150NeetCode 150

117.Longest Increasing Path in a Matrix

Hard2-D Dynamic Programming · 7/11
LeetCode #329Video

Problem

Given an m x n integer matrix, return the length of the longest strictly increasing path.

From each cell you may move up, down, left or right (no diagonals, no wrapping around the border). Each step must go to a cell with a strictly larger value.

Examples

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

Constraints

  • m == matrix.length, n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31 - 1

💡 Key Insight

Draw an edge from each cell to every strictly larger neighbour. Because values strictly increase along edges, this graph is a DAG — no cycles — so lip(cell) = 1 + max(lip(larger neighbour)) is well defined and has no circular dependencies. Memoizing it makes every cell computed once (O(m·n)). The same DAG can also be processed iteratively with topological sort (peel off local maxima layer by layer), where the number of layers is the answer.

Recursion (Brute Force)

TimeExponential in the worst caseSpaceO(m · n)

Intuition

From every starting cell, DFS into each strictly larger neighbour and take the longest result. No visited set is needed — a strictly increasing path can never revisit a cell.

Algorithm

  1. For each cell (r, c), compute dfs(r, c):
    • best = 1.
    • For each of the 4 neighbours (nr, nc) inside the grid with matrix[nr][nc] > matrix[r][c]: best = max(best, 1 + dfs(nr, nc)).
  2. Return the maximum over all cells.

Visualization

flowchart TD
    A["start at 1 (2,1)"] --> B["2 (2,0)"]
    A --> C["6 (1,1)"]
    B --> D["6 (1,0)"]
    D --> E["9 (0,0)<br/>dead end, len 1"]
    C --> F["9 (0,1) len 1"]
    C --> G["8 (1,2) len 1"]
    E --> H["path 1→2→6→9 = 4"]

Starting from different cells recomputes the same sub-paths (e.g. everything above 6) again and again.

Code

java
class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int longestIncreasingPath(int[][] matrix) {
        int best = 0;
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                best = Math.max(best, dfs(matrix, r, c));
            }
        }
        return best;
    }

    private int dfs(int[][] matrix, int r, int c) {
        int best = 1; // the cell itself
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < matrix.length && nc >= 0 && nc < matrix[0].length
                    && matrix[nr][nc] > matrix[r][c]) {
                best = Math.max(best, 1 + dfs(matrix, nr, nc));
            }
        }
        return best;
    }
}

Complexity

  • Time: Exponential in the worst case — e.g. a snake-like increasing matrix makes each start explore long overlapping paths, up to O(4^(m·n)) branching bounds.
  • Space: O(m · n) — recursion depth can equal the path length.

Complexity Comparison

Approach Time Space
Recursion (Brute Force) Exponential O(m · n)
Top-Down Memoization O(m · n) O(m · n)
Bottom-Up DP by Sorted Value O(m · n · log(m · n)) O(m · n)
Topological Sort (Kahn's BFS) O(m · n) O(m · n)

Common Pitfalls

  • Adding a visited set during DFS — unnecessary (strict increase prevents cycles) and it breaks memoization if you reset it wrongly.
  • Using >= instead of > — equal neighbours are not allowed and would create cycles.
  • Using 0 as both "unvisited" and a real answer — fine here only because every real answer is at least 1.
  • Deep recursion on a 200 x 200 snake-shaped matrix can approach 40,000 frames; the BFS version avoids stack overflow risk.
  • In Kahn's algorithm, counting nodes processed instead of layers — the answer is the number of BFS levels.