Problem Statement in English

You’re given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all four directions (up, down, left, right) if the value of the adjacent cell is strictly greater than the value of the current cell.

Return the number of increasing paths in the grid. Since the answer may be very large, return it modulo $10^9 + 7$.

Approach

You’ll notice that we can build the answer for each cell as 1 + the sum of the answers for all adjacent cells with a strictly greater value.

This is a good place to use a dynamic programming approach with memoization.

We’ll define a recursive function dp(i, j) that returns the number of increasing paths starting from cell (i, j).

We simply explore all four possible directions from the current cell. If the adjacent cell has a strictly greater value, we add 1 + dp(nei_x, nei_y) to our result, where (nei_x, nei_y) are the coordinates of the neighboring cell.

Finally, we sum up the results of dp(i, j) for all cells in the grid to get the total number of increasing paths.

And we’re done.

Solution in Python


class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        M = len(grid)
        N = len(grid[0])
        MOD = 10 ** 9 + 7
        directions = [(0,1), (1,0), (0,-1), (-1,0)]
        
        @cache
        def dp(i, j):
            res = 0
            for dx, dy in directions:
                nx, ny = i + dx, j + dy

                if 0 <= nx < M and 0 <= ny < N and grid[i][j] < grid[nx][ny]:
                    res += 1 + dp(nx, ny)
                    res %= MOD

            return res

        res = M*N

        for i in range(M):
            for j in range(N):
                res += dp(i, j)
                res %= MOD

        return res

Complexity

  • Time: $O(M \times N)$
    Since we iterate over each cell and each cell’s result is computed only once and stored in the cache. There are a total of $M*N$ cells.

  • Space: $O(M \times N)$
    Since our cache has to store the result for each cell in the grid, which takes up $O(M \times N)$ space.

And we are done.