Number of Increasing Paths in a Grid solution and explanation
9 more videos on this problem
Number of Increasing Paths in a Grid | DFS + Memo | ADOBE, MICROSOFT | Leetcode-2328 | Live CodecodestorywithMIK · 24:38 · 8K views
Number of Increasing Paths in a Grid II DFS II DP II Graph II Recursion II Leetcode 2328Aryan Mittal · 16:36 · 4K views
Weekly Contest 300 | 2328. Number of Increasing Paths in a GridcodingMohan · 23:14 · 1K views
Weekly Contest 300 | Leetcode 2328 Number of Increasing Paths in a Grid | Easy DPCoding Decoded · 6:49 · 1K views
2328. Number of Increasing Paths in a Grid | Recursion | LeetCode Daily ChallengeDeep Tech · 16:37 · 1K views
Number of Increasing Paths in a Grid | Leetcode - 2328Algorithms Made Easy · 14:16 · 987 views
Number of Increasing Paths in a Grid | 2328 LeetCode | Dp | Leetcode Weekly Contest 300CodeWithSunny · 13:23 · 978 views
Number of Increasing Paths in a Grid - Leetcode 2328 - PythonTechError · 10:19 · 630 views
2328. Number of Increasing Paths in a Grid (Leetcode Hard)Programming Live with Larry · 10:40 · 581 views
Daily Leetcode #1174: Jun 18, 2023 - 2328. Number of Increasing Paths in a GridProgramming Live with Larry · 5:31 · 436 views
The problem
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
Approach overview
Problem 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 1: DFS with Memoization
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.
MOD = 10**9 + 7
def count_paths(grid):
m, n = len(grid), len(grid[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
dp = [[-1]*n for _ in range(m)]
def dfs(x, y):
if dp[x][y] != -1:
return dp[x][y]
path_count = 1 # count the path of length 1 (itself)
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > grid[x][y]:
path_count = (path_count + dfs(nx, ny)) % MOD
dp[x][y] = path_count
return dp[x][y]
total_paths = 0
for i in range(m):
for j in range(n):
total_paths = (total_paths + dfs(i, j)) % MOD
return total_paths
# Example Usage
grid = [[1, 1], [3, 4]]
print(count_paths(grid)) # Output: 8const MOD = 10**9 + 7;
function countPaths(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = Array.from({ length: m }, () => Array(n).fill(-1));
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
function dfs(x, y) {
if (dp[x][y] !== -1) return dp[x][y];
let pathCount = 1; // path of length 1 (itself)
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > grid[x][y]) {
pathCount = (pathCount + dfs(nx, ny)) % MOD;
}
}
dp[x][y] = pathCount;
return dp[x][y];
}
let totalPaths = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
totalPaths = (totalPaths + dfs(i, j)) % MOD;
}
}
return totalPaths;
}
// Example Usage
const grid = [[1, 1], [3, 4]];
console.log(countPaths(grid)); // Output: 8The 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.
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.
Approach 2: Topological Sort with Dynamic Programming
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.
import java.util.*;
public class NumberOfIncreasingPaths {
private static final int MOD = 1_000_000_007;
public int countPaths(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] paths = new int[m][n];
for (int[] row : paths) Arrays.fill(row, 1);
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});
}
}
Collections.sort(cells, (a, b) -> Integer.compare(grid[a[0]][a[1]], grid[b[0]][b[1]]));
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int[] cell : cells) {
int x = cell[0], y = cell[1];
for (int[] d : directions) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > grid[x][y]) {
paths[nx][ny] = (paths[nx][ny] + paths[x][y]) % MOD;
}
}
}
int totalPaths = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
totalPaths = (totalPaths + paths[i][j]) % MOD;
}
}
return totalPaths;
}
// Example Usage
// public static void main(String[] args) {
// int[][] grid = {{1, 1}, {3, 4}};
// System.out.println(new NumberOfIncreasingPaths().countPaths(grid)); // Output: 8
// }
}#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
int countPaths(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> paths(m, vector<int>(n, 1));
vector<pair<int, int>> cells;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cells.emplace_back(i, j);
}
}
sort(cells.begin(), cells.end(), [&](pair<int, int> a, pair<int, int> b) {
return grid[a.first][a.second] < grid[b.first][b.second];
});
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (auto [x, y] : cells) {
for (auto [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > grid[x][y]) {
paths[nx][ny] = (paths[nx][ny] + paths[x][y]) % MOD;
}
}
}
int total_paths = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
total_paths = (total_paths + paths[i][j]) % MOD;
}
}
return total_paths;
}
// Example Usage
// vector<vector<int>> grid = {{1, 1}, {3, 4}};
// cout << countPaths(grid) << endl; // Output: 8This Java solution follows a similar algorithm to the C++ implementation. It begins by initializing a 'paths' array where each cell starts with a count of 1. It uses a list of cell coordinates, sorted by grid values. Each cell's neighboring cells are then updated based on condition checks of increasing values, ensuring correct path accumulation before summing across the grid.
Time Complexity: O(m*n*log(m*n)), due to sorting the grid cells.
Space Complexity: O(m*n) for storing paths.
Approach 3: DFS + Memorization
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:
- If
f[i][j]is not0, it means that it has been calculated, andf[i][j]is returned directly; - Otherwise, we initialize
f[i][j] = 1, and then enumerate the four directions of(i, j). If the grid(x, y)in a certain direction satisfies0 leq x \lt m,0 leq y \lt n, andgrid[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, sof[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.
function countPaths(grid: number[][]): number {
const mod = 1e9 + 7;
const m = grid.length;
const n = grid[0].length;
const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
const dfs = (i: number, j: number): number => {
if (f[i][j]) {
return f[i][j];
}
let ans = 1;
const dirs: number[] = [-1, 0, 1, 0, -1];
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const 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);
};
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
ans = (ans + dfs(i, j)) % mod;
}
}
return ans;
}func countPaths(grid [][]int) (ans int) {
const mod = 1e9 + 7
m, n := len(grid), len(grid[0])
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
var dfs func(int, int) int
dfs = func(i, j int) int {
if f[i][j] != 0 {
return f[i][j]
}
f[i][j] = 1
dirs := [5]int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y] {
f[i][j] = (f[i][j] + dfs(x, y)) % mod
}
}
return f[i][j]
}
for i, row := range grid {
for j := range row {
ans = (ans + dfs(i, j)) % mod
}
}
return
}Complexity comparison
| 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)), due to sorting the grid cells. Space Complexity: O(m*n) for storing paths. |
| DFS + Memorization | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Number of Increasing Paths in a Grid easy or hard?
LeetCode classifies this problem as Hard. The difficulty comes from recognizing that the grid forms a DAG and that dynamic programming with memoized DFS or topological processing is required to avoid exponential path enumeration.
Number of Increasing Paths in a Grid Python/Java solution
Python implementations typically use DFS with memoization and recursion caching. Java or C++ solutions often implement either the same memoized DFS or a topological sort with dynamic programming over the grid values. Both approaches achieve O(m*n) time complexity.
How to solve Number of Increasing Paths in a Grid in O(n)?
The problem can be solved in O(m*n) time using DFS with memoization or topological dynamic programming. Each cell contributes once to the DP state, and transitions only happen to larger neighbors. Because the grid forms a DAG of increasing edges, dynamic programming efficiently aggregates path counts.
What is the best approach for Number of Increasing Paths in a Grid?
DFS with memoization is the most common and interview-friendly approach. Each cell runs a DFS that explores neighbors with larger values, while a DP cache stores the number of paths starting from that cell. This prevents recomputation and reduces the complexity to O(m*n).
Is Number of Increasing Paths in a Grid asked at Google/Amazon/Meta?
Grid dynamic programming and graph traversal problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variations involving increasing paths, DAG DP, or memoized DFS are common in senior-level algorithm rounds.
What data structure is used in Number of Increasing Paths in a Grid?
The solution uses a grid-based DP table along with recursion or graph traversal. DFS relies on memoization arrays, while the alternative solution models the grid as a directed acyclic graph and processes nodes using topological ordering.
What is the time complexity of Number of Increasing Paths in a Grid?
The optimal solutions run in O(m*n) time where m and n are grid dimensions. Each cell is processed once, and at most four neighbors are checked. Memoization or topological DP ensures repeated subproblems are reused instead of recomputed.