Skip to content

2328. Number of Increasing Paths in a Grid

SourceWeekly Contest 300 Q4DifficultyHardRating2001

Description

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.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 105
  • 1 <= grid[i][j] <= 105

Solutions

Solution 1: DFS + Memorization

Thinking

Strictly increasing paths may start anywhere and have any length. Up to \(10^5\) cells makes enumeration impossible. Paths from a cell depend only on strictly larger neighbors.

Memoize \(dfs(i,j)\) as one (the cell itself) plus the four larger neighbors. Each cell is solved once; the sum over the grid is the answer.

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.

 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    private int[][] f;
    private int[][] grid;
    private int m;
    private int n;
    private final int mod = (int) 1e9 + 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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}

Solution 2: Sorting + Dynamic Programming

Thinking

Strictly increasing paths may start at any cell. The grid has up to \(10^5\) cells. Memoizing a walk toward larger neighbors follows one chain on a strictly increasing row of length \(1000\), and both \(m\) and \(n\) can be \(1000\), which exhausts the call stack.

The bottleneck is that chain: every call steps into a strictly larger neighbor that has not been finished.

The count at a cell depends only on strictly larger neighbors, so those edges form a DAG.

Sort cells by decreasing value. Set \(f[i][j]=1\), then add the finished counts of the four larger neighbors and reduce modulo \(10^9+7\). The sum of every \(f[i][j]\), reduced again, is the number of paths.

Let \(f[i][j]\) be the number of strictly increasing paths that start at row \(i\) and column \(j\). A cell contributes one path by itself, so the initial value is \(1\). It may also step to a strictly larger neighbor, which gives

\[ f[i][j] = 1 + \sum_{\substack{(x,y)\sim(i,j)\\ grid[i][j] < grid[x][y]}} f[x][y] \pmod{10^9+7}. \]

A larger cell does not depend on the current one. Processing cells from largest value to smallest finishes those neighbors first. The answer is \(\sum f[i][j]\) modulo \(10^9+7\).

The time complexity is \(O(mn \log(mn))\), and the space complexity is \(O(mn)\). Here \(m\) and \(n\) are the number of rows and columns.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        mod = 10**9 + 7
        m, n = len(grid), len(grid[0])
        f = [[1] * n for _ in range(m)]
        cells = [(grid[i][j], i, j) for i in range(m) for j in range(n)]
        cells.sort(reverse=True)
        dirs = (-1, 0, 1, 0, -1)
        for _, i, j in cells:
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[i][j] < grid[x][y]:
                    f[i][j] = (f[i][j] + f[x][y]) % mod
        return sum(sum(row) for row in f) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int countPaths(int[][] grid) {
        final int mod = (int) 1e9 + 7;
        int m = grid.length, n = grid[0].length;
        int[][] f = new int[m][n];
        int[][] cells = new int[m * n][3];
        for (int i = 0, k = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                f[i][j] = 1;
                cells[k][0] = grid[i][j];
                cells[k][1] = i;
                cells[k][2] = j;
                ++k;
            }
        }
        Arrays.sort(cells, (a, b) -> Integer.compare(b[0], a[0]));
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int[] cell : cells) {
            int i = cell[1], j = cell[2];
            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]) {
                    f[i][j] = (f[i][j] + f[x][y]) % mod;
                }
            }
        }
        long ans = 0;
        for (int[] row : f) {
            for (int v : row) {
                ans += v;
            }
        }
        return (int) (ans % mod);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int countPaths(vector<vector<int>>& grid) {
        const int mod = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> f(m, vector<int>(n, 1));
        vector<array<int, 3>> cells;
        cells.reserve(m * n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                cells.push_back({grid[i][j], i, j});
            }
        }
        sort(cells.begin(), cells.end(), [](const array<int, 3>& a, const array<int, 3>& b) {
            return a[0] > b[0];
        });
        int dirs[5] = {-1, 0, 1, 0, -1};
        for (auto& cell : cells) {
            int i = cell[1], j = cell[2];
            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]) {
                    f[i][j] = (f[i][j] + f[x][y]) % mod;
                }
            }
        }
        long long ans = 0;
        for (auto& row : f) {
            for (int v : row) {
                ans += v;
            }
        }
        return ans % mod;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func countPaths(grid [][]int) int {
    const mod = 1e9 + 7
    m, n := len(grid), len(grid[0])
    f := make([][]int, m)
    cells := make([][3]int, 0, m*n)
    for i := 0; i < m; i++ {
        f[i] = make([]int, n)
        for j := 0; j < n; j++ {
            f[i][j] = 1
            cells = append(cells, [3]int{grid[i][j], i, j})
        }
    }
    sort.Slice(cells, func(a, b int) bool { return cells[a][0] > cells[b][0] })
    dirs := [5]int{-1, 0, 1, 0, -1}
    for _, cell := range cells {
        i, j := cell[1], cell[2]
        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] + f[x][y]) % mod
            }
        }
    }
    ans := 0
    for _, row := range f {
        for _, v := range row {
            ans = (ans + v) % mod
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function countPaths(grid: number[][]): number {
    const mod = 1e9 + 7;
    const m = grid.length;
    const n = grid[0].length;
    const f: number[][] = Array.from({ length: m }, () => Array(n).fill(1));
    const cells: number[][] = [];
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            cells.push([grid[i][j], i, j]);
        }
    }
    cells.sort((a, b) => b[0] - a[0]);
    const dirs = [-1, 0, 1, 0, -1];
    for (const [_, i, j] of cells) {
        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]) {
                f[i][j] = (f[i][j] + f[x][y]) % mod;
            }
        }
    }
    let ans = 0;
    for (const row of f) {
        for (const v of row) {
            ans = (ans + v) % mod;
        }
    }
    return ans;
}

Comments