Number of Increasing Paths in a Grid - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

HardArray Dynamic Programming Depth-First Search Breadth-First Search15 min readAsked at: Microsoft, Adobe

Practice this problem

Problem Statement

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 10⁹ + 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.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

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.

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.

Code

Python JavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(m*n*log(m*n)), primarily due to sorting m*n cells.

Space Complexity: O(m*n) for the paths storage.

Try this approach in the editor →

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 not 0, it means that it has been calculated, and f[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 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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
DFS with Memoization	Time Complexity: O(mn), where m and n are the dimensions of the grid. Each cell is visited once. Space Complexity: O(mn) due to the memoization table.
Topological Sort with Dynamic Programming	Time Complexity: O(mnlog(mn)), primarily due to sorting mn cells. Space Complexity: O(m*n) for the paths storage.
DFS + Memorization	—

Detailed 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

Video Solution

Number of Increasing Paths in a Grid | DFS + Memo | ADOBE, MICROSOFT | Leetcode-2328 | Live Code • codestorywithMIK • 8,517 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Number of Increasing Paths in a Grid with our built-in code editor and test cases.

Practice on FleetCode

All Paths From Source to Target

Longest Increasing Path in a Matrix

Problem Info

DifficultyHard

Acceptance57.4%

Approaches3

Reading time15 min

Asked at

Microsoft Adobe

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: DFS with Memoization

Code

Complexity

Approach 2: Topological Sort with Dynamic Programming

Code

Complexity

Approach 3: DFS + Memorization

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents