# Number of Increasing Paths in a Grid
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-increasing-paths-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/number-of-increasing-paths-in-a-grid
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, Matrix, Graph
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-increasing-paths-in-a-grid/image0.png) 

**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:**

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

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 1000`
* `1 <= m * n <= 105`
* `1 <= grid[i][j] <= 105`

# Approaches
## Brute-Force Depth First Search
The most straightforward approach is to use a brute-force Depth First Search (DFS). The problem asks for the total number of increasing paths, which can start and end at any cell. This is equivalent to summing the number of increasing paths that start from each individual cell.

We can define a recursive function `dfs(row, col)` that counts the number of increasing paths starting from the cell at `(row, col)`. For each cell in the grid, we initiate a DFS from it. The total count is the sum of the results from these DFS calls.
**Time:** O(4^(m*n))
For each cell, the DFS can potentially branch into three directions (excluding the one it came from). This leads to an exponential number of path explorations and function calls, making it highly inefficient. · **Space:** O(m * n)
In the worst-case scenario (e.g., a path that traverses every cell in the grid), the recursion depth can be up to `m * n`. This determines the space used by the call stack.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient due to a massive number of redundant computations.; Will result in a 'Time Limit Exceeded' error for all but the smallest input grids.
### Explanation
The `dfs(row, col)` function calculates the number of paths starting at `(row, col)`. A path can be of length 1 (the cell itself), so we initialize the count to 1. Then, we explore all four adjacent cells (up, down, left, right). If a neighbor `(newRow, newCol)` has a value strictly greater than `grid[row][col]`, we can extend the current path to it. Any increasing path starting from `(newRow, newCol)` can be appended. Therefore, we recursively call `dfs(newRow, newCol)` and add its result to our count. The main function iterates through every cell of the grid, calls the `dfs` function, and accumulates the results. This approach explores all possible paths, but it re-computes the number of paths for the same cell multiple times if that cell is reachable from different paths.

```java
class Solution {
    int m, n;
    int[][] grid;
    int MOD = 1_000_000_007;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int countPaths(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        long totalPaths = 0;

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

    private long dfs(int r, int c) {
        long count = 1; // Path of length 1 starting and ending at (r, c)
        for (int[] dir : dirs) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] > grid[r][c]) {
                count = (count + dfs(nr, nc)) % MOD;
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a global variable `totalPaths` to 0.
*   Iterate through each cell `(i, j)` in the grid.
*   For each cell, call a recursive helper function, `dfs(i, j)`, which calculates the number of increasing paths starting from that cell.
*   Add the result of `dfs(i, j)` to `totalPaths`, taking the result modulo `10^9 + 7` at each addition.
*   The `dfs(row, col)` function works as follows:
    1.  Initialize a local variable `count` to 1. This represents the path of length one consisting of the cell `(row, col)` itself.
    2.  Iterate through the four adjacent neighbors `(newRow, newCol)`.
    3.  For each neighbor, check if it's within the grid boundaries and if `grid[newRow][newCol] > grid[row][col]`.
    4.  If the conditions are met, it's a valid next step in an increasing path. Recursively call `dfs(newRow, newCol)` and add the returned value to `count`.
    5.  After checking all neighbors, return the final `count`.

## Dynamic Programming with Sorting
This approach uses bottom-up dynamic programming. We can define `dp[i][j]` as the number of increasing paths that *end* at cell `(i, j)`. A path ending at `(i, j)` is formed by taking a path that ends at an adjacent cell `(k, l)` with a smaller value (`grid[k][l] < grid[i][j]`) and extending it to `(i, j)`. The base case is a path of length 1, which is just the cell `(i, j)` itself.

To ensure that when we calculate `dp[i][j]`, the values for all necessary neighbors are already computed, we must process the cells in a specific order. By sorting the cells based on their values in ascending order, we guarantee that we always compute the `dp` value for a cell before it's needed by a cell with a larger value.
**Time:** O(m * n * log(m * n))
The dominant operation is sorting all `m * n` cells, which takes O(m*n * log(m*n)) time. The subsequent iteration over the cells takes O(m * n) time. · **Space:** O(m * n)
We need O(m * n) space for the `dp` table and another O(m * n) space to store the list of cells for sorting.
**Pros:** A valid DP approach that is significantly more efficient than brute force.; Avoids recursion, which can prevent stack overflow issues on certain systems or with specific grid structures.
**Cons:** The time complexity is dominated by the sorting step, making it less efficient than the optimal O(m*n) solution.
### Explanation
First, we create a list of all cell coordinates and sort them based on their grid values. We then initialize a `dp` table of the same dimensions as the grid, where `dp[i][j]` will store the number of increasing paths ending at `(i, j)`. We initialize every `dp[i][j]` to 1, as each cell itself constitutes a path of length one.

We then iterate through the sorted cells. For each cell `(r, c)`, we consider its neighbors `(nr, nc)`. If `grid[nr][nc] > grid[r][c]`, it means we can extend any path ending at `(r, c)` to `(nr, nc)`. So, we add the number of paths ending at `(r, c)` (which is `dp[r][c]`) to the number of paths ending at `(nr, nc)` (i.e., `dp[nr][nc] = (dp[nr][nc] + dp[r][c]) % MOD`).

After iterating through all the cells, the `dp` table is fully populated. The total number of increasing paths in the grid is the sum of all `dp[i][j]` values, as any path must end at some cell.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public int countPaths(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int MOD = 1_000_000_007;

        List<int[]> cells = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cells.add(new int[]{i, j});
            }
        }

        // Sort cells by their values in ascending order
        Collections.sort(cells, (a, b) -> grid[a[0]][a[1]] - grid[b[0]][b[1]]);

        long[][] dp = new long[m][n];
        for (long[] row : dp) {
            Arrays.fill(row, 1); // Each cell is a path of length 1
        }
        
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        for (int[] cell : cells) {
            int r = cell[0];
            int c = cell[1];

            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] > grid[r][c]) {
                    dp[nr][nc] = (dp[nr][nc] + dp[r][c]) % MOD;
                }
            }
        }
        
        long totalPaths = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                totalPaths = (totalPaths + dp[i][j]) % MOD;
            }
        }

        return (int) totalPaths;
    }
}
```
### Algorithm
*   Define `dp[i][j]` as the number of strictly increasing paths ending at cell `(i, j)`.
*   The recurrence relation is `dp[i][j] = 1 + sum(dp[k][l])` for all adjacent neighbors `(k, l)` where `grid[k][l] < grid[i][j]`.
*   To compute `dp[i][j]` correctly, we need the `dp` values of neighbors with smaller grid values to be available. This can be achieved by processing cells in increasing order of their values.
*   Create a list of all cell coordinates `(r, c)`.
*   Sort this list based on the cell values `grid[r][c]` in ascending order.
*   Initialize a `dp` table of size `m x n`, with all values set to 1 (representing the path of length 1 for each cell).
*   Iterate through the sorted list of cells `(r, c)`:
    *   For each neighbor `(nr, nc)` of `(r, c)` with `grid[nr][nc] > grid[r][c]`, update `dp[nr][nc]` by adding `dp[r][c]` to it. This means any path ending at `(r, c)` can be extended to `(nr, nc)`.
*   The total number of paths is the sum of all values in the `dp` table.

## Dynamic Programming with Memoization (Top-Down)
This approach, also known as top-down dynamic programming, optimizes the brute-force DFS by eliminating redundant computations. The brute-force solution repeatedly calculates the number of paths for the same cell. We can avoid this by storing the result for each cell `(i, j)` the first time it's computed and reusing this stored result for subsequent calls.

We use a 2D array, `memo`, of the same size as the grid to act as a cache. `memo[i][j]` will store the number of increasing paths starting from cell `(i, j)`. When our DFS function is called for a cell, it first checks the memoization table. If a valid result is found, it's returned immediately, otherwise, the result is computed, stored in the table, and then returned.
**Time:** O(m * n)
Each state `(i, j)` is computed exactly once. The computation for each state involves a constant number of operations (checking 4 neighbors). Therefore, the total time complexity is proportional to the number of cells. · **Space:** O(m * n)
This space is used for the memoization table `memo` and the recursion call stack. The recursion depth can be at most `m * n`.
**Pros:** Optimal time complexity, as each subproblem is solved only once.; It's a direct and intuitive optimization of the brute-force recursive solution.
**Cons:** The recursive implementation might lead to a stack overflow error if the path depth is very large, although this is unlikely given the problem constraints.
### Explanation
We define a recursive function `dfs(r, c)` that computes the number of increasing paths starting from `(r, c)`. A 2D array `memo` is used to store these results. `memo[r][c] = 0` will indicate that the value for cell `(r, c)` has not been computed yet (since path counts are always at least 1).

Inside `dfs(r, c)`, we first check `memo[r][c]`. If it's non-zero, we return the cached value. Otherwise, we calculate the value: start with `count = 1` (for the path containing only the cell `(r, c)` itself). Then, for each valid neighbor `(nr, nc)` with a strictly greater value, we recursively call `dfs(nr, nc)` and add the result to `count`. Before returning, we store the computed `count` in `memo[r][c]`. The main function iterates through every cell, calls `dfs` for each, and sums the results to get the total number of paths.

Because each cell's `dfs` result is computed only once, the overall time complexity is significantly reduced.

```java
class Solution {
    int m, n;
    int[][] grid;
    long[][] memo;
    int MOD = 1_000_000_007;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int countPaths(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        this.memo = new long[m][n]; // memo[i][j] = 0 means not computed
        
        long totalPaths = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                totalPaths = (totalPaths + dfs(i, j)) % MOD;
            }
        }
        return (int) totalPaths;
    }

    private long dfs(int r, int c) {
        // If already computed, return the stored result
        if (memo[r][c] != 0) {
            return memo[r][c];
        }

        // Each cell itself is a path of length 1
        long count = 1; 

        // Explore neighbors with strictly greater values
        for (int[] dir : dirs) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] > grid[r][c]) {
                count = (count + dfs(nr, nc)) % MOD;
            }
        }
        
        // Store the result and return
        memo[r][c] = count;
        return count;
    }
}
```
### Algorithm
*   Define `dp[i][j]` as the number of strictly increasing paths starting from cell `(i, j)`.
*   The recurrence relation is `dp[i][j] = 1 + sum(dp[k][l])` for all adjacent neighbors `(k, l)` where `grid[k][l] > grid[i][j]`.
*   Use a memoization table, `memo[m][n]`, initialized with a sentinel value (e.g., 0) to store the results of `dp[i][j]`.
*   The main function iterates through all cells `(i, j)` and sums up the results of a recursive helper function `dfs(i, j)`.
*   The `dfs(row, col)` function:
    1.  Check if `memo[row][col]` has been computed. If so, return the stored value.
    2.  Initialize `count = 1` (for the path of length 1).
    3.  Explore the 4 adjacent neighbors `(newRow, newCol)`.
    4.  If a neighbor is valid and `grid[newRow][newCol] > grid[row][col]`, recursively call `dfs(newRow, newCol)` and add its result to `count`.
    5.  Store the final `count` in `memo[row][col]` before returning it.

# Solutions
### Java

```java
class Solution {
private
  int[][] f;
private
  int[][] grid;
private
  int m;
private
  int n;
private
  final int mod = (int)1 e9 + 7;
public
  int countPaths(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    f = new int[m][n];
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = (ans + dfs(i, j)) % mod;
      }
    }
    return ans;
  }
private
  int dfs(int i, int j) {
    if (f[i][j] != 0) {
      return f[i][j];
    }
    int ans = 1;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) {
        ans = (ans + dfs(x, y)) % mod;
      }
    }
    return f[i][j] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countPaths(vector<vector<int>> &grid) {
    const int mod = 1e9 + 7;
    int m = grid.size(), n = grid[0].size();
    int f[m][n];
    memset(f, 0, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (f[i][j]) {
        return f[i][j];
      }
      int ans = 1;
      int dirs[5] = {-1, 0, 1, 0, -1};
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) {
          ans = (ans + dfs(x, y)) % mod;
        }
      }
      return f[i][j] = ans;
    };
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = (ans + dfs(i, j)) % mod;
      }
    }
    return ans;
  }
};

```

### Python

```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

```