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.
This approach uses Depth First Search (DFS) combined with memoization to count the number of increasing paths starting from each cell. The main idea is to recursively explore each cell's neighbors, moving to the next cell only if its value is higher, and storing intermediate results to avoid redundant calculations.
The Python solution implements DFS with memoization to explore each cell's increasing paths. A 2D list 'dp' stores the number of paths starting from each cell and is initialized to -1. The function 'dfs' calculates paths from the starting cell using recursion and updating the 'dp' table to avoid redundant calculations. Results are computed modulo 10^9 + 7 to handle large path counts.
Python
JavaScript
Time Complexity: O(m*n), where m and n are the dimensions of the grid. Each cell is visited once.
Space Complexity: O(m*n) due to the memoization table.
This approach involves sorting the cells of the grid based on their values and then using dynamic programming to calculate the number of increasing paths from each cell. By processing cells in increasing order, we ensure that when calculating the number of paths for a cell, all smaller cells have been processed.
The C++ solution performs topological sorting based on grid values. It initially sets up each cell with a path count of 1. Cells are processed in value order using a vector of pairs, sorted by their value. For each cell, we explore adjacent cells that contain larger values, updating path counts as we go, ensuring earlier cells' paths are calculated before later ones, thus respecting dependencies.
Time Complexity: O(m*n*log(m*n)), primarily due to sorting m*n cells.
Space Complexity: O(m*n) for the paths storage.
We design a function dfs(i, j), which represents the number of strictly increasing paths that can be reached from the grid graph starting at the i-th row and j-th column. Then the answer is sum_{i=0}^{m-1} sum_{j=0}^{n-1} dfs(i, j). In the search process, we can use a two-dimensional array f to record the calculated results to avoid repeated calculation.
The calculation process of the function dfs(i, j) is as follows:
f[i][j] is not 0, it means that it has been calculated, and f[i][j] is returned directly;f[i][j] = 1, and then enumerate the four directions of (i, j). If the grid (x, y) in a certain direction satisfies 0 leq x \lt m, 0 leq y \lt n, and grid[i][j] \lt grid[x][y], we can start from the grid (i, j) to the grid (x, y), and the number on the path is strictly increasing, so f[i][j] += dfs(x, y).Finally, we return f[i][j].
The answer is sum_{i=0}^{m-1} sum_{j=0}^{n-1} dfs(i, j).
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the grid graph, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| DFS with Memoization | Time Complexity: O(m*n), where m and n are the dimensions of the grid. Each cell is visited once. Space Complexity: O(m*n) due to the memoization table. |
| Topological Sort with Dynamic Programming | Time Complexity: O(m*n*log(m*n)), primarily due to sorting m*n cells. Space Complexity: O(m*n) for the paths storage. |
| DFS + Memorization | — |
| 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 |
Number of Increasing Paths in a Grid | DFS + Memo | ADOBE, MICROSOFT | Leetcode-2328 | Live Code • codestorywithMIK • 7,467 views views
Watch 9 more video solutions →Practice Number of Increasing Paths in a Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor