Watch 10 video solutions for Number of Increasing Paths in a Grid, a hard level problem involving Array, Dynamic Programming, Depth-First Search. This walkthrough by codestorywithMIK has 7,467 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions.
Return the number of strictly increasing paths in the grid such that you can start from any cell and end at any cell. Since the answer may be very large, return it modulo 109 + 7.
Two paths are considered different if they do not have exactly the same sequence of visited cells.
Example 1:
Input: grid = [[1,1],[3,4]] Output: 8 Explanation: The strictly increasing paths are: - Paths with length 1: [1], [1], [3], [4]. - Paths with length 2: [1 -> 3], [1 -> 4], [3 -> 4]. - Paths with length 3: [1 -> 3 -> 4]. The total number of paths is 4 + 3 + 1 = 8.
Example 2:
Input: grid = [[1],[2]] Output: 3 Explanation: The strictly increasing paths are: - Paths with length 1: [1], [2]. - Paths with length 2: [1 -> 2]. The total number of paths is 2 + 1 = 3.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 1051 <= grid[i][j] <= 105Problem Overview: Given an m x n grid, count the number of strictly increasing paths. A path can start and end at any cell, and you can move in four directions. The challenge is avoiding recomputation because many paths share subproblems.
Approach 1: DFS with Memoization (O(m*n) time, O(m*n) space)
Treat each cell as the start of a path and run Depth-First Search to explore neighbors with strictly larger values. The key insight: the number of increasing paths starting from a cell depends only on its higher-valued neighbors. Cache results in a dp[r][c] table so each cell is computed once. Each DFS explores at most four directions, and memoization converts the exponential search into linear work over the grid. This is a classic Dynamic Programming on a directed acyclic graph formed by increasing edges.
Approach 2: Topological Sort with Dynamic Programming (O(m*n) time, O(m*n) space)
Model the grid as a DAG where an edge goes from a smaller value cell to a larger neighbor. Since edges always go to larger values, cycles cannot exist. Sort cells by value (or process them using in-degree with Topological Sort). Initialize each cell with one path (the cell itself). When processing a cell, propagate its path count to neighbors with larger values. This effectively performs bottom-up dynamic programming over the graph. Each edge is processed once, giving linear complexity relative to the number of cells.
Recommended for interviews: DFS with memoization is the most common explanation because it directly models “paths starting from this cell.” It shows understanding of recursion, caching, and DAG-based dynamic programming. The topological DP approach demonstrates deeper graph insight and works well when you prefer iterative solutions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Memoization | O(m*n) | O(m*n) | Best general solution; easy to reason about increasing paths starting from each cell |
| Topological Sort + Dynamic Programming | O(m*n) | O(m*n) | Useful when modeling the grid as a DAG and solving iteratively |