#2328

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Number of Increasing Paths in a Grid

Solve Number of Increasing Paths in a Grid by turning cell comparisons into a DAG and counting paths with topological DP.

array dynamic programming depth first search breadth first search graph

Problem Statement

You are given a matrix of integers, and from any position you may move up, down, left, or right to a neighboring cell. A path is valid only when every next cell has a strictly larger value than the current one, and you may choose any cell as the starting point.

Your task is to count all distinct strictly increasing paths in the grid, where two paths differ if their visited cell sequence is different. Because the total can grow very quickly across many overlapping increasing branches, return the result modulo 1000000007.

Examples

Example 1

Input: grid = [[1,1],[3,4]]

Output: 8

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

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 <= 105
1 <= grid[i][j] <= 105

Solution Approach

Model the grid as a DAG of increasing moves

Treat each cell as a node. For every adjacent pair, direct an edge from the smaller value to the larger value, because only that move can appear in a strictly increasing path. Equal values create no edge, which is important because allowing them would break the acyclic structure this problem depends on.

Use indegrees to process cells in topological order

Compute each cell's indegree as the number of smaller neighbors that can flow into it. Start a queue with indegree-zero cells, which are local minima. Initialize each cell's path count to 1 since the single-cell path is always valid, then pop cells in topological order and push their counts to larger neighbors while decreasing indegrees.

Accumulate path counts with modular DP

When processing a cell, add its current path count into every strictly larger adjacent cell because every path ending here can be extended by one move. Once a neighbor's indegree becomes zero, it is ready because all smaller predecessors have already contributed. Sum all DP values at the end, taking modulo 1000000007 after each addition to avoid overflow.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Let $N = m \times n$ . Each cell is processed once, and each of its up to four neighbors is checked a constant number of times while building indegrees and propagating counts, so the time complexity is $O(N)$ . The space complexity is $O(N)$ for the indegree structure, DP counts, and queue. This is the right trade-off for this problem because repeated DFS from every cell without memoization would revisit the same increasing suffixes too many times.

What Interviewers Usually Probe

They want you to notice the grid forms a DAG because values must strictly increase on every move.
A strong answer explains why each cell starts with one path before extending counts to larger neighbors.
If you mention both memoized DFS and indegree topological DP, then justify why the graph ordering is clean here, that is usually a positive signal.

Common Pitfalls or Variants

Common pitfalls

Forgetting that every single cell counts as its own increasing path, which undercounts examples like [[1],[2]].
Adding edges between equal values or using non-strict comparisons, which creates invalid transitions for this exact problem.
Applying modulo only at the very end, which risks overflow and makes intermediate DP updates incorrect in large grids.

Follow-up variants

Solve the same grid by memoized DFS where dp[i][j] stores the number of increasing paths starting at cell (i, j).
Count decreasing paths instead by reversing the comparison direction or flipping edge construction.
Return the longest increasing path length instead of the total count, which changes the DP transition from summation to maximization.

FAQ

What is the key pattern in Number of Increasing Paths in a Grid?

The core pattern is graph indegree plus topological ordering. Strictly increasing moves guarantee a DAG, so you can process cells from smaller layers to larger layers and accumulate path counts without cycles.

Why does each cell start with a DP value of 1?

A single cell is already a valid strictly increasing path of length one. That base contribution is necessary before extending paths into larger neighbors, otherwise every answer will be short by the number of cells.

Can I solve this problem with DFS and memoization instead?

Yes. Memoized DFS is a standard alternative where each state returns the number of increasing paths starting from that cell. The topological approach is often easier to reason about iteratively when you want explicit DAG processing.

Why are equal neighboring values ignored?

The problem requires strictly increasing paths, so moving from a value to the same value is illegal. Ignoring equal-value neighbors is what preserves the DAG property and prevents invalid transitions.

What makes this problem hard instead of a basic grid DP?

The difficulty comes from overlapping path suffixes across many start cells and from the fact that movement is not limited to a fixed direction like right or down. You need to exploit the value-based ordering of the grid, not the row and column layout alone.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)) % mod

Continue Practicing

#329 longest increasing path in a matrix #1728 cat and mouse ii #2556 disconnect path in a binary matrix by at most one flip