2328. Number of Increasing Paths in a Grid

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.

Solution¶

Overview¶

• A cell itself is also a valid path, so each cell in the grid stands for a unique path.
• The path must be strictly increasing, so the paths colored in red are invalid.

Approach 1: Sorting + DP.¶

Intuition¶

Let’s build an auxiliary array dp of the same size as grid to represent the number of paths that end at each cell. Initially, the value of each dp[i][j] cell is 1, which stands for the path made by grid[i][j] cell itself.

Then, for each cell grid[i][j], we need to look for its neighbor cells in 4 directions, if there exists a neighbor cell (let’s say grid[i + 1][j]) that is larger than grid[i][j], it means every path that ends at grid[i][j] can be extended to grid[i + 1][j]. Therefore, the number of paths ending at grid[i + 1][j] should be incremented by grid[i][j].

However, if we traverse all cells by arbitrary order, we might need many repeated updates, as described below.

It implies that we should iterate over all cells by value. If we sort these cells by value, then traverse over them from the smallest. This ensures that the number of paths ending at each cell in dp is updated only once.

Algorithm¶

1. Initialize dp, a 2-d array of the same size as grid, and set every value as 1.
2. Sort all cells by value and iterate over the sorted cells.
3. For each cell grid[i][j], check its 4-direction neighbor cells, if a neighbor cell grid[curr_i][curr_j] has a larger value, then increment dp[curr_i][curr_j] by dp[i][j].
4. Return the sum of all cells of dp when the iteration ends.

Implementation¶

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        mod = 10 ** 9 + 7
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0|0, 1], [0, -1], [1, 0], [-1, 0]]

        # Initialize dp, 1 stands for the path made by a cell itself.
        dp = [[1] * n for _ in range(m)]

        # Sort all cells by value.
        cell_list = [[i, j] for i in range(m) for j in range(n)]
        cell_list.sort(key = lambda x: grid[x[0]][x[1]])

        # Iterate over the sorted cells, for each cell grid[i][j]: 
        for i, j in cell_list:
            # Check its four neighbor cells, if a neighbor cell grid[curr_i][curr_j] has a
            # larger value, increment dp[curr_i][curr_j] by dp[i][j]
            for di, dj in directions:
                curr_i, curr_j = i + di, j + dj
                if 0 <= curr_i < m and 0 <= curr_j < n and grid[curr_i][curr_j] > grid[i][j]:
                    dp[curr_i][curr_j] += dp[i][j]
                    dp[curr_i][curr_j] %= mod

        # Sum over dp[i][j].
        return sum(sum(row) % mod for row in dp) % mod

Complexity Analysis¶

Let m×n be the size of the input array grid.

1. Time complexity: O(m⋅n⋅log(m⋅n))

   • We sort all cells by value, it takes O(klogk) to sort an array of size O(k), so it takes O(m⋅n⋅log(m⋅n)) time.
   • The iteration over sorted cells has O(m⋅n) steps, each step consists of checking at most four neighbor cells, thus it takes O(m⋅n) time.
   • For initialization of dp and the calculation of answer we iterate over all the cells of the dp array, which also takes O(m⋅n) time.
   • To sum up, the overall time complexity is O(m⋅n⋅log(m⋅n)).

2. Space complexity: O(m⋅n)

   • We used two arrays, cellList and dp, they both contain O(m⋅n) elements.