Number of Increasing Paths in a Grid

Number of Increasing Paths in a Grid

What is this problem about?

The Number of Increasing Paths in a Grid problem gives you a matrix of integers. Count the number of strictly increasing paths (of any length ≥ 1) — paths where each step moves to an adjacent cell (4 directions) with a strictly larger value. Return the count modulo 10^9+7. This hard coding problem uses DFS with memoization on a DAG formed by the grid.

Why is this asked in interviews?

Microsoft and Adobe ask this because it combines grid DFS with memoization on a DAG — the grid's cells form a directed acyclic graph where edges go from smaller to larger values. The array, matrix, BFS, graph, memoization, DFS, topological sort, and dynamic programming interview pattern is comprehensively exercised.

Algorithmic pattern used

Memoized DFS (top-down DP). dp[r][c] = number of increasing paths starting from cell (r,c). For each cell, the paths starting here = 1 (the cell itself) + sum of dp[nr][nc] for all 4 neighbors (nr,nc) where grid[nr][nc] > grid[r][c]. Use memoization to avoid recomputation. Process in increasing order via topological sort or let memoized DFS handle it naturally.

Example explanation

Grid:

1 2
3 4

• dp[0][0]=1 (just cell 1): paths going through 1→2→4, 1→3→4, 1→2, 1→3, 1→4, 1→3→4... carefully:
• dp[1][1] (value=4)=1 (only itself).
• dp[0][1] (value=2): 1 + dp[1][1]=2.
• dp[1][0] (value=3): 1 + dp[1][1]=2.
• dp[0][0] (value=1): 1 + dp[0][1] + dp[1][0] = 1+2+2=5. Total = sum all dp = 5+2+2+1 = 10.

Common mistakes candidates make

• Not memoizing (exponential time without it).
• Counting each path multiple times (each path counted exactly once at its starting cell).
• Using BFS instead of DFS memoization (BFS is harder to memoize here).
• Off-by-one: each cell contributes at least 1 to its own dp value.

Interview preparation tip

Counting paths on a DAG (directed acyclic graph) always uses DP in topological order or memoized DFS. When the grid values define a natural topological order (smaller values come before larger), memoized DFS from each cell handles it automatically — you never revisit a cell with a larger value before computing its smaller-value predecessors. Practice "number of paths in a DAG" problems — they form a family with "longest increasing path," "number of increasing paths," and "path counting in directed graphs."