How hard is LeetCode 2328. Number of Increasing Paths in a Grid?

LeetCode 2328. Number of Increasing Paths in a Grid is rated Hard on LeetCode.

What is the time complexity of LeetCode 2328. Number of Increasing Paths in a Grid?

The Python solution on this page runs in O(m \times n).

What is the space complexity of LeetCode 2328. Number of Increasing Paths in a Grid?

The Python solution on this page uses O(m \times n) auxiliary space.

Number of Increasing Paths in a Grid — LeetCode 2328 Python Solution

HardDepth-First SearchBreadth-First SearchGraphTopological SortMemoizationArrayDynamic ProgrammingMatrix

Problem: #2328
Pattern: Topological Sort
Reading time: 3 min
Source: leetcode.com

The 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.

Example

Input: grid = [[1,1],[3,4]]
Output: 8
Explanation: The strictly increasing paths are:

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(m \times n)
Space	O(m \times n) auxiliary

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 2328. Number of Increasing Paths in a Grid is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2328. Number of Increasing Paths in a Grid?: LeetCode 2328. Number of Increasing Paths in a Grid is rated Hard on LeetCode.
What is the time complexity of LeetCode 2328. Number of Increasing Paths in a Grid?: The Python solution on this page runs in O(m \times n).
What is the space complexity of LeetCode 2328. Number of Increasing Paths in a Grid?: The Python solution on this page uses O(m \times n) auxiliary space.
What topics does LeetCode 2328. Number of Increasing Paths in a Grid cover?: LeetCode 2328. Number of Increasing Paths in a Grid is tagged Depth-First Search, Breadth-First Search, Graph, Topological Sort, Memoization, Array, Dynamic Programming and Matrix on LeetCode.