# Longest Increasing Path in a Matrix

- **Canonical ID**: `longest-increasing-path-in-a-matrix`
- **Canonical URL**: https://dsacheatsheet.com/problems/longest-increasing-path-in-a-matrix
- **Difficulty**: hard
- **Patterns**: 2D DP, Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

## 1. Core Invariant / The Trick

Strictly increasing edges `matrix[nr][nc] > matrix[r][c]` guarantee the implicit graph is a **DAG** (no cycles are possible!). Therefore no `visited` set is needed — plain memoized DFS (`cache[r][c]`) computes every cell’s longest path once.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(M * N)`
- **Space Complexity**: `O(M * N)`
- **Proof**: Because strictly increasing paths cannot revisit a cell, every vertex out-edge is evaluated once and memoized in O(MN).

## 3. Minimal Idiomatic Code

### Python
```python
def longestIncreasingPath(matrix: list[list[int]]) -> int:
    R, C = len(matrix), len(matrix[0])
    memo = [[0] * C for _ in range(R)]
    def dfs(r: int, c: int) -> int:
        if memo[r][c]:
            return memo[r][c]
        best = 1
        cur = matrix[r][c]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and matrix[nr][nc] > cur:
                best = max(best, 1 + dfs(nr, nc))
        memo[r][c] = best
        return best
    return max(dfs(r, c) for r in range(R) for c in range(C))
```

### TypeScript
```typescript
export function longestIncreasingPath(matrix: number[][]): number {
  const R = matrix.length, C = matrix[0].length;
  const memo = Array.from({ length: R }, () => new Int32Array(C));
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  const dfs = (r: number, c: number): number => {
    if (memo[r][c] !== 0) return memo[r][c];
    let best = 1;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < R && nc >= 0 && nc < C && matrix[nr][nc] > matrix[r][c]) {
        best = Math.max(best, 1 + dfs(nr, nc));
      }
    }
    return (memo[r][c] = best);
  };
  let ans = 0;
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) ans = Math.max(ans, dfs(r, c));
  return ans;
}
```

### C++
```cpp
int longestIncreasingPath(vector<vector<int>>& m) {
    int R = m.size(), C = m[0].size(), ans = 0;
    vector<vector<int>> memo(R, vector<int>(C));
    int dr[4] = {1,-1,0,0}, dc[4] = {0,0,1,-1};
    auto dfs = [&](auto& self, int r, int c) -> int {
        if (memo[r][c]) return memo[r][c];
        int best = 1;
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && m[nr][nc] > m[r][c])
                best = max(best, 1 + self(self, nr, nc));
        }
        return memo[r][c] = best;
    };
    for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c) ans = max(ans, dfs(dfs, r, c));
    return ans;
}
```

### Java
```java
int longestIncreasingPath(int[][] m) {
    int R = m.length, C = m[0].length, ans = 0;
    int[][] memo = new int[R][C];
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++) ans = Math.max(ans, dfs(m, memo, r, c));
    return ans;
}
int dfs(int[][] m, int[][] memo, int r, int c) {
    if (memo[r][c] != 0) return memo[r][c];
    int best = 1, R = m.length, C = m[0].length;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < R && nc >= 0 && nc < C && m[nr][nc] > m[r][c])
            best = Math.max(best, 1 + dfs(m, memo, nr, nc));
    }
    return memo[r][c] = best;
}
```

### Go
```go
func longestIncreasingPath(m [][]int) int {
    R, C := len(m), len(m[0])
    memo := make([][]int, R)
    for i := range R { memo[i] = make([]int, C) }
    dirs := [4][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    var dfs func(int, int) int
    dfs = func(r, c int) int {
        if memo[r][c] != 0 { return memo[r][c] }
        best := 1
        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            if nr >= 0 && nr < R && nc >= 0 && nc < C && m[nr][nc] > m[r][c] {
                best = max(best, 1+dfs(nr, nc))
            }
        }
        memo[r][c] = best
        return best
    }
    ans := 0
    for r := range R { for c := range C { ans = max(ans, dfs(r, c)) } }
    return ans
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Adding a mutable `visited` bitmask breaks memoization correctness because different entry paths wouldn’t share cached results.
- Using `>=` instead of `>` creates cycles on equal-value adjacent cells.

### Follow-ups
- Iterative topological peel (Kahn’s algorithm on grid cells ordered by uphill indegree) runs layer-by-layer without recursion stack overflow.