Number of Increasing Paths in a Grid
HardPrompt
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] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to use a brute-force Depth First Search (DFS). The problem asks for the total number of increasing paths, which can start and end at any cell. This is equivalent to summing the number of increasing paths that start from each individual cell.
We can define a recursive function dfs(row, col) that counts the number of increasing paths starting from the cell at (row, col). For each cell in the grid, we initiate a DFS from it. The total count is the sum of the results from these DFS calls.
Algorithm
- Initialize a global variable
totalPathsto 0. - Iterate through each cell
(i, j)in the grid. - For each cell, call a recursive helper function,
dfs(i, j), which calculates the number of increasing paths starting from that cell. - Add the result of
dfs(i, j)tototalPaths, taking the result modulo10^9 + 7at each addition. - The
dfs(row, col)function works as follows:- Initialize a local variable
countto 1. This represents the path of length one consisting of the cell(row, col)itself. - Iterate through the four adjacent neighbors
(newRow, newCol). - For each neighbor, check if it's within the grid boundaries and if
grid[newRow][newCol] > grid[row][col]. - If the conditions are met, it's a valid next step in an increasing path. Recursively call
dfs(newRow, newCol)and add the returned value tocount. - After checking all neighbors, return the final
count.
- Initialize a local variable
Walkthrough
The dfs(row, col) function calculates the number of paths starting at (row, col). A path can be of length 1 (the cell itself), so we initialize the count to 1. Then, we explore all four adjacent cells (up, down, left, right). If a neighbor (newRow, newCol) has a value strictly greater than grid[row][col], we can extend the current path to it. Any increasing path starting from (newRow, newCol) can be appended. Therefore, we recursively call dfs(newRow, newCol) and add its result to our count. The main function iterates through every cell of the grid, calls the dfs function, and accumulates the results. This approach explores all possible paths, but it re-computes the number of paths for the same cell multiple times if that cell is reachable from different paths.
class Solution { int m, n; int[][] grid; int MOD = 1_000_000_007; int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public int countPaths(int[][] grid) { this.m = grid.length; this.n = grid[0].length; this.grid = grid; long totalPaths = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { totalPaths = (totalPaths + dfs(i, j)) % MOD; } } return (int) totalPaths; } private long dfs(int r, int c) { long count = 1; // Path of length 1 starting and ending at (r, c) for (int[] dir : dirs) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] > grid[r][c]) { count = (count + dfs(nr, nc)) % MOD; } } return count; }}Complexity
Time
O(4^(m*n)) For each cell, the DFS can potentially branch into three directions (excluding the one it came from). This leads to an exponential number of path explorations and function calls, making it highly inefficient.
Space
O(m * n) In the worst-case scenario (e.g., a path that traverses every cell in the grid), the recursion depth can be up to `m * n`. This determines the space used by the call stack.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Extremely inefficient due to a massive number of redundant computations.
Will result in a 'Time Limit Exceeded' error for all but the smallest input grids.
This approach uses bottom-up dynamic programming. We can define dp[i][j] as the number of increasing paths that end at cell (i, j). A path ending at (i, j) is formed by taking a path that ends at an adjacent cell (k, l) with a smaller value (grid[k][l] < grid[i][j]) and extending it to (i, j). The base case is a path of length 1, which is just the cell (i, j) itself.
To ensure that when we calculate dp[i][j], the values for all necessary neighbors are already computed, we must process the cells in a specific order. By sorting the cells based on their values in ascending order, we guarantee that we always compute the dp value for a cell before it's needed by a cell with a larger value.
Algorithm
- Define
dp[i][j]as the number of strictly increasing paths ending at cell(i, j). - The recurrence relation is
dp[i][j] = 1 + sum(dp[k][l])for all adjacent neighbors(k, l)wheregrid[k][l] < grid[i][j]. - To compute
dp[i][j]correctly, we need thedpvalues of neighbors with smaller grid values to be available. This can be achieved by processing cells in increasing order of their values. - Create a list of all cell coordinates
(r, c). - Sort this list based on the cell values
grid[r][c]in ascending order. - Initialize a
dptable of sizem x n, with all values set to 1 (representing the path of length 1 for each cell). - Iterate through the sorted list of cells
(r, c):- For each neighbor
(nr, nc)of(r, c)withgrid[nr][nc] > grid[r][c], updatedp[nr][nc]by addingdp[r][c]to it. This means any path ending at(r, c)can be extended to(nr, nc).
- For each neighbor
- The total number of paths is the sum of all values in the
dptable.
Walkthrough
First, we create a list of all cell coordinates and sort them based on their grid values. We then initialize a dp table of the same dimensions as the grid, where dp[i][j] will store the number of increasing paths ending at (i, j). We initialize every dp[i][j] to 1, as each cell itself constitutes a path of length one.
We then iterate through the sorted cells. For each cell (r, c), we consider its neighbors (nr, nc). If grid[nr][nc] > grid[r][c], it means we can extend any path ending at (r, c) to (nr, nc). So, we add the number of paths ending at (r, c) (which is dp[r][c]) to the number of paths ending at (nr, nc) (i.e., dp[nr][nc] = (dp[nr][nc] + dp[r][c]) % MOD).
After iterating through all the cells, the dp table is fully populated. The total number of increasing paths in the grid is the sum of all dp[i][j] values, as any path must end at some cell.
import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List; class Solution { public int countPaths(int[][] grid) { int m = grid.length; int n = grid[0].length; int MOD = 1_000_000_007; List<int[]> cells = new ArrayList<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cells.add(new int[]{i, j}); } } // Sort cells by their values in ascending order Collections.sort(cells, (a, b) -> grid[a[0]][a[1]] - grid[b[0]][b[1]]); long[][] dp = new long[m][n]; for (long[] row : dp) { Arrays.fill(row, 1); // Each cell is a path of length 1 } int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; for (int[] cell : cells) { int r = cell[0]; int c = cell[1]; for (int[] dir : dirs) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] > grid[r][c]) { dp[nr][nc] = (dp[nr][nc] + dp[r][c]) % MOD; } } } long totalPaths = 0; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { totalPaths = (totalPaths + dp[i][j]) % MOD; } } return (int) totalPaths; }}Complexity
Time
O(m * n * log(m * n)) The dominant operation is sorting all `m * n` cells, which takes O(m*n * log(m*n)) time. The subsequent iteration over the cells takes O(m * n) time.
Space
O(m * n) We need O(m * n) space for the `dp` table and another O(m * n) space to store the list of cells for sorting.
Trade-offs
Pros
A valid DP approach that is significantly more efficient than brute force.
Avoids recursion, which can prevent stack overflow issues on certain systems or with specific grid structures.
Cons
The time complexity is dominated by the sorting step, making it less efficient than the optimal O(m*n) solution.
This approach, also known as top-down dynamic programming, optimizes the brute-force DFS by eliminating redundant computations. The brute-force solution repeatedly calculates the number of paths for the same cell. We can avoid this by storing the result for each cell (i, j) the first time it's computed and reusing this stored result for subsequent calls.
We use a 2D array, memo, of the same size as the grid to act as a cache. memo[i][j] will store the number of increasing paths starting from cell (i, j). When our DFS function is called for a cell, it first checks the memoization table. If a valid result is found, it's returned immediately, otherwise, the result is computed, stored in the table, and then returned.
Algorithm
- Define
dp[i][j]as the number of strictly increasing paths starting from cell(i, j). - The recurrence relation is
dp[i][j] = 1 + sum(dp[k][l])for all adjacent neighbors(k, l)wheregrid[k][l] > grid[i][j]. - Use a memoization table,
memo[m][n], initialized with a sentinel value (e.g., 0) to store the results ofdp[i][j]. - The main function iterates through all cells
(i, j)and sums up the results of a recursive helper functiondfs(i, j). - The
dfs(row, col)function:- Check if
memo[row][col]has been computed. If so, return the stored value. - Initialize
count = 1(for the path of length 1). - Explore the 4 adjacent neighbors
(newRow, newCol). - If a neighbor is valid and
grid[newRow][newCol] > grid[row][col], recursively calldfs(newRow, newCol)and add its result tocount. - Store the final
countinmemo[row][col]before returning it.
- Check if
Walkthrough
We define a recursive function dfs(r, c) that computes the number of increasing paths starting from (r, c). A 2D array memo is used to store these results. memo[r][c] = 0 will indicate that the value for cell (r, c) has not been computed yet (since path counts are always at least 1).
Inside dfs(r, c), we first check memo[r][c]. If it's non-zero, we return the cached value. Otherwise, we calculate the value: start with count = 1 (for the path containing only the cell (r, c) itself). Then, for each valid neighbor (nr, nc) with a strictly greater value, we recursively call dfs(nr, nc) and add the result to count. Before returning, we store the computed count in memo[r][c]. The main function iterates through every cell, calls dfs for each, and sums the results to get the total number of paths.
Because each cell's dfs result is computed only once, the overall time complexity is significantly reduced.
class Solution { int m, n; int[][] grid; long[][] memo; int MOD = 1_000_000_007; int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public int countPaths(int[][] grid) { this.m = grid.length; this.n = grid[0].length; this.grid = grid; this.memo = new long[m][n]; // memo[i][j] = 0 means not computed long totalPaths = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { totalPaths = (totalPaths + dfs(i, j)) % MOD; } } return (int) totalPaths; } private long dfs(int r, int c) { // If already computed, return the stored result if (memo[r][c] != 0) { return memo[r][c]; } // Each cell itself is a path of length 1 long count = 1; // Explore neighbors with strictly greater values for (int[] dir : dirs) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] > grid[r][c]) { count = (count + dfs(nr, nc)) % MOD; } } // Store the result and return memo[r][c] = count; return count; }}Complexity
Time
O(m * n) Each state `(i, j)` is computed exactly once. The computation for each state involves a constant number of operations (checking 4 neighbors). Therefore, the total time complexity is proportional to the number of cells.
Space
O(m * n) This space is used for the memoization table `memo` and the recursion call stack. The recursion depth can be at most `m * n`.
Trade-offs
Pros
Optimal time complexity, as each subproblem is solved only once.
It's a direct and intuitive optimization of the brute-force recursive solution.
Cons
The recursive implementation might lead to a stack overflow error if the path depth is very large, although this is unlikely given the problem constraints.
Solutions
Solution
class Solution {private int[][] f;private int[][] grid;private int m;private int n;private final int mod = (int)1 e9 + 7;public int countPaths(int[][] grid) { m = grid.length; n = grid[0].length; this.grid = grid; f = new int[m][n]; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { ans = (ans + dfs(i, j)) % mod; } } return ans; }private int dfs(int i, int j) { if (f[i][j] != 0) { return f[i][j]; } int ans = 1; int[] dirs = {-1, 0, 1, 0, -1}; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) { ans = (ans + dfs(x, y)) % mod; } } return f[i][j] = ans; }}class Solution {public: int countPaths(vector<vector<int>> &grid) { const int mod = 1e9 + 7; int m = grid.size(), n = grid[0].size(); int f[m][n]; memset(f, 0, sizeof(f)); function<int(int, int)> dfs = [&](int i, int j) -> int { if (f[i][j]) { return f[i][j]; } int ans = 1; int dirs[5] = {-1, 0, 1, 0, -1}; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) { ans = (ans + dfs(x, y)) % mod; } } return f[i][j] = ans; }; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { ans = (ans + dfs(i, j)) % mod; } } return ans; }};class Solution: def countPaths(self, grid: List[List[int]]) -> int: @ cache def dfs(i: int, j: int) -> int: ans = 1 for a, b in pairwise((- 1, 0, 1, 0, - 1)): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[i][j] < grid[x][y]: ans = (ans + dfs(x, y)) % mod return ans mod = 10 ** 9 + 7 m, n = len(grid), len(grid[0]) return sum(dfs(i, j) for i in range(m) for j in range(n)) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.