We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Increasing Paths in a Grid

Number: 2409

Difficulty: Hard

Paid? No

Companies: Amazon, Adobe

Problem Description

Given an m x n integer matrix grid, you can move from a cell to any of its 4 adjacent neighbors (up, down, left, right). A strictly increasing path is a sequence of cells where each subsequent cell has a value greater than the previous one. Count the total number of strictly increasing paths in the grid (a path can start and end at any cell), and return the result modulo 10^9 + 7.

Key Insights

  • Every single cell is a valid increasing path of length one.
  • The movement is allowed in all four directions; the condition is that the next value must be strictly greater.
  • Use Depth-First Search (DFS) with memoization (or dynamic programming) to count paths starting from each cell.
  • Since a cell’s optimal result may overlap with neighbor computations, caching the results avoids redundant calculations.
  • The grid values themselves impose a natural order, allowing a topological-style processing if needed.

Space and Time Complexity

Time Complexity: O(m * n) since each cell is processed once and each DFS considers 4 directions. Space Complexity: O(m * n) for the memoization table and recursion stack (in worst-case scenarios).

Solution

We use DFS with memoization to count the number of increasing paths starting from each cell. For each cell, if it hasn't been computed before (i.e., memoized), we count one path (the cell itself) plus the paths obtainable by moving in any valid (increasing) direction. The computed result for each cell is stored in a dp table to prevent recalculating overlapping subproblems. Finally, sum the number of paths from all cells, applying modulo 10^9 + 7 at each step.

Code Solutions

def countPaths(grid):
    MOD = 10**9 + 7
    m, n = len(grid), len(grid[0])
    dp = [[-1] * n for _ in range(m)]
    # Directions: down, up, right, left
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    # Increase recursion limit if necessary.
    import sys
    sys.setrecursionlimit(10**6)
    
    # DFS function to compute paths starting at cell (i, j)
    def dfs(i, j):
        if dp[i][j] != -1:
            return dp[i][j]
        total = 1  # Count the cell itself as a valid path
        for dx, dy in directions:
            x, y = i + dx, j + dy
            if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:
                total = (total + dfs(x, y)) % MOD
        dp[i][j] = total
        return total
    
    result = 0
    for i in range(m):
        for j in range(n):
            result = (result + dfs(i, j)) % MOD
    return result
← Back to All Questions