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.

Examples

Example 1:

$$ \begin{bmatrix} 1 & 1 \\ 3 & 4 \end{bmatrix} $$

1
2
3
4
5
6
7
8
9

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:

$$ \begin{bmatrix} 1 \\ 2 \end{bmatrix} $$

1
2
3
4
5
6
7
8

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.

Solution

Method 1 - Using DP

Here is the approach:

  1. Problem Understanding:
    • You have an m x n matrix.
    • You can move from a cell to any directly adjacent cell (left, right, up, down).
    • The paths need to be strictly increasing.
    • The result should be the number of such paths modulo (10^9 + 7).
  2. Dynamic Programming with Memoization:
    • We’ll use dynamic programming to solve this problem efficiently.
    • Let’s define dp[i][j] as the number of strictly increasing paths starting from cell (i, j).
    • We’ll need to compute dp[i][j] for all cells (i, j).
  3. Steps:
    • Use depth-first search (DFS) to explore all possible paths starting from each cell.
    • Memoize the results to avoid recomputing paths from the same cell multiple times.
    • The total number of paths is the sum of paths starting from each cell in the matrix.
  4. Edge Cases:
    • Single cell matrix.
    • All elements in the matrix are the same.

Code

 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
37
38
39

class Solution {
    private static final int MOD = 1_000_000_007;
    private int m, n;
    private int[][] dp, grid;
    
    private int dfs(int i, int j) {
        if (dp[i][j] != -1) return dp[i][j];
        dp[i][j] = 1; // Each cell itself is a path

        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] dir : directions) {
            int x = i + dir[0], y = j + dir[1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > grid[i][j]) {
                dp[i][j] = (dp[i][j] + dfs(x, y)) % MOD;
            }
        }

        return dp[i][j];
    }

    public int countPaths(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        this.dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            Arrays.fill(dp[i], -1);
        }

        int result = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                result = (result + dfs(i, j)) % MOD;
            }
        }

        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

MOD = 10**9 + 7

class Solution:
    def countPaths(self, grid):
        m, n = len(grid), len(grid[0])
        dp = [[-1] * n for _ in range(m)]

        def dfs(i, j):
            if dp[i][j] != -1:
                return dp[i][j]
            dp[i][j] = 1  # Each cell itself is a path

            for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:
                    dp[i][j] = (dp[i][j] + dfs(x, y)) % MOD

            return dp[i][j]

        result = 0
        for i in range(m):
            for j in range(n):
                result = (result + dfs(i, j)) % MOD

        return result

Complexity

  • ⏰ Time complexity: O(m * n)  since each cell is processed once and its result is memoized.
  • 🧺 Space complexity: O(m * n) for the memoization table.