# Longest Increasing Path in a Matrix
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-increasing-path-in-a-matrix)
Canonical: https://scaleengineer.com/dsa/problems/longest-increasing-path-in-a-matrix
**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
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Nvidia](https://scaleengineer.com/companies/nvidia), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Snap](https://scaleengineer.com/companies/snap), [WeRide](https://scaleengineer.com/companies/weride)
---
## Problem
Given an `m x n` integers `matrix`, return _the length of the longest increasing path in_ `matrix`.

From each cell, you can either move in four directions: left, right, up, or down. You **may not** move **diagonally** or move **outside the boundary** (i.e., wrap-around is not allowed).

**Example 1:**

![](https://assets.glich.co/dsa/longest-increasing-path-in-a-matrix/image0.jpg) 

**Input:** matrix = [[9,9,4],[6,6,8],[2,1,1]]
**Output:** 4
**Explanation:** The longest increasing path is `[1, 2, 6, 9]`.

**Example 2:**

![](https://assets.glich.co/dsa/longest-increasing-path-in-a-matrix/image1.jpg) 

**Input:** matrix = [[3,4,5],[3,2,6],[2,2,1]]
**Output:** 4
**Explanation:** The longest increasing path is `[3, 4, 5, 6]`. Moving diagonally is not allowed.

**Example 3:**

**Input:** matrix = [[1]]
**Output:** 1

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 200`
* `0 <= matrix[i][j] <= 231 - 1`

# Approaches
## Brute-Force Depth First Search
This approach explores every possible increasing path starting from every cell in the matrix. For each cell, it performs a Depth First Search (DFS) to find the longest path originating from it. The overall maximum length found among all starting cells is the answer.
**Time:** O((m*n) * 4^(m*n)) - This is a loose upper bound, but the complexity is exponential. From each cell, the search can branch out, and the same subproblems (finding the longest path from a particular cell) are solved repeatedly. This leads to an exponential number of function calls. · **Space:** O(m * n) - The space is dominated by the recursion stack depth, which in the worst case (a path that visits every cell) can be the total number of cells in the matrix.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to a massive number of redundant computations.; Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest matrices.
### Explanation
We define a main function that iterates through every cell `(i, j)` of the matrix. For each cell, it calls a recursive DFS helper function, `dfs(row, col)`, to compute the length of the longest increasing path starting at `(row, col)`. The main function keeps track of the maximum length found so far and updates it after each DFS call.

The `dfs(row, col)` function explores the four adjacent neighbors (up, down, left, right). For each neighbor `(nextRow, nextCol)` that is within the matrix boundaries and has a value greater than `matrix[row][col]`, it makes a recursive call. The length of the path starting from `(row, col)` is `1 + max(length of paths from valid neighbors)`. The base case for the recursion is a cell from which no further increasing path can be formed; in this case, the path length is 1 (the cell itself).

This method is straightforward but highly inefficient because it repeatedly calculates the longest path for the same cells multiple times. For example, the longest path from cell `A` might be needed to calculate the path from cell `B`, and also later for the path from cell `C`.

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

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        m = matrix.length;
        n = matrix[0].length;
        int maxLength = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxLength = Math.max(maxLength, dfs(matrix, i, j));
            }
        }
        return maxLength;
    }

    private int dfs(int[][] matrix, int row, int col) {
        int maxPath = 1;
        for (int[] dir : dirs) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && matrix[newRow][newCol] > matrix[row][col]) {
                maxPath = Math.max(maxPath, 1 + dfs(matrix, newRow, newCol));
            }
        }
        return maxPath;
    }
}
```
### Algorithm
1. Initialize a global variable `maxLength` to 0.
2. Create a main function that iterates through every cell `(i, j)` of the matrix.
3. For each cell, call a recursive DFS helper function, `dfs(row, col)`, to compute the length of the longest increasing path starting at that cell.
4. Update `maxLength = max(maxLength, result from dfs)`.
5. The `dfs(row, col)` function works as follows:
    a. Initialize `maxPathFromCell` to 1 (for the cell itself).
    b. Explore the four adjacent neighbors (up, down, left, right).
    c. For each neighbor `(nextRow, nextCol)` that is within the matrix boundaries and has a value `matrix[nextRow][nextCol] > matrix[row][col]`, make a recursive call: `1 + dfs(nextRow, nextCol)`.
    d. Update `maxPathFromCell` with the maximum length found among all valid neighbors.
    e. Return `maxPathFromCell`.
6. After iterating through all cells, return `maxLength`.

## Depth First Search with Memoization (Dynamic Programming)
This approach significantly optimizes the brute-force DFS by using memoization, a top-down dynamic programming technique. We use a cache (a 2D array) to store the length of the longest increasing path starting from each cell. This avoids recomputing the result for the same cell multiple times, drastically improving performance.
**Time:** O(m * n) - Each cell's result is computed exactly once. The main loops iterate through all `m*n` cells. The `dfs` function for each cell `(i, j)` runs its main logic only once before its result is cached. During this run, it performs constant work (checking four neighbors). Therefore, the total time is proportional to the number of cells. · **Space:** O(m * n) - This space is used for the `memo` cache which stores the result for each cell, and for the recursion stack. The recursion depth can be up to `m*n` in the worst case.
**Pros:** Highly efficient and optimal solution.; Guaranteed to pass within typical time limits by eliminating redundant computations.; It correctly identifies and solves the overlapping subproblems inherent in the problem.
**Cons:** Requires extra space for the memoization table.; The recursion stack can be deep for certain matrix configurations, though this is also true for the brute-force approach.
### Explanation
The overall structure is similar to the brute-force approach: iterate through all cells and perform a DFS from each to find the longest path. The key difference is the addition of a `memo` cache, a 2D array of the same dimensions as the input matrix, initialized to 0. `memo[i][j]` will store the length of the longest increasing path starting at cell `(i, j)`.

The modified `dfs(row, col)` function first checks if `memo[row][col]` is non-zero. If it is, it means we have already computed the result for this cell, so we can return the cached value immediately. If the result is not in the cache, we compute it just like in the brute-force approach: explore all valid neighbors, make recursive calls, and find the maximum path length. Before returning the computed length, we store it in `memo[row][col]` so it can be reused later.

By caching the results, we ensure that the DFS for each cell is computed exactly once. This transforms the exponential complexity of the brute-force approach into a linear one.

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

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        m = matrix.length;
        n = matrix[0].length;
        int[][] memo = new int[m][n];
        int maxLength = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxLength = Math.max(maxLength, dfs(matrix, i, j, memo));
            }
        }
        return maxLength;
    }

    private int dfs(int[][] matrix, int row, int col, int[][] memo) {
        if (memo[row][col] != 0) {
            return memo[row][col];
        }
        
        int maxPath = 1;
        for (int[] dir : dirs) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && matrix[newRow][newCol] > matrix[row][col]) {
                maxPath = Math.max(maxPath, 1 + dfs(matrix, newRow, newCol, memo));
            }
        }
        
        memo[row][col] = maxPath;
        return maxPath;
    }
}
```
### Algorithm
1. Initialize a memoization cache `memo[m][n]` with all values as 0. A value of 0 indicates the result for that cell has not been computed.
2. Initialize a global variable `maxLength` to 0.
3. Iterate through every cell `(i, j)` of the matrix.
4. For each cell, call a recursive DFS helper function, `dfs(row, col, matrix, memo)`.
5. Update `maxLength = max(maxLength, result from dfs)`.
6. The `dfs(row, col, matrix, memo)` function:
    a. If `memo[row][col]` is not 0, it means we have already computed the result. Return the cached value `memo[row][col]` immediately.
    b. Otherwise, initialize `maxPathFromCell` to 1.
    c. Explore the four adjacent neighbors.
    d. For each valid neighbor `(nextRow, nextCol)` with a greater value, recursively call `dfs(nextRow, nextCol, matrix, memo)` and update `maxPathFromCell = max(maxPathFromCell, 1 + result)`.
    e. Before returning, store the computed result: `memo[row][col] = maxPathFromCell`.
    f. Return `maxPathFromCell`.
7. After iterating through all cells, return `maxLength`.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][] matrix;
private
  int[][] f;
public
  int longestIncreasingPath(int[][] matrix) {
    m = matrix.length;
    n = matrix[0].length;
    f = new int[m][n];
    this.matrix = matrix;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = Math.max(ans, dfs(i, j));
      }
    }
    return ans;
  }
private
  int dfs(int i, int j) {
    if (f[i][j] != 0) {
      return f[i][j];
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k];
      int y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
        f[i][j] = Math.max(f[i][j], dfs(x, y));
      }
    }
    return ++f[i][j];
  }
}

```

### CPP

```cpp
class Solution { public: int longestIncreasingPath ( vector < vector < int >>& matrix ) { int m = matrix . size (), n = matrix [ 0 ]. size (); int f [ m ][ n ]; memset ( f , 0 , sizeof ( f )); int ans = 0 ; int dirs [ 5 ] = { - 1 , 0 , 1 , 0 , - 1 }; function < int ( int , int ) > dfs = [ & ]( int i , int j ) -> int { if ( f [ i ][ j ]) { return f [ i ][ j ]; } 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 && matrix [ x ][ y ] > matrix [ i ][ j ]) { f [ i ][ j ] = max ( f [ i ][ j ], dfs ( x , y )); } } return ++ f [ i ][ j ]; }; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { ans = max ( ans , dfs ( i , j )); } } return ans ; } };
```

### Python

```python
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int: @ cache def dfs(i: int, j: int) -> int: ans = 0 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 matrix[x][y] > matrix[i][j]: ans = max(ans, dfs(x, y)) return ans + 1 m, n = len(matrix), len(matrix[0]) return max(dfs(i, j) for i in range(m) for j in range(n))

```