Longest Increasing Path in Matrix LeetCode 329

LeetCode 329 — Longest Increasing Path in a Matrix — gives you an m x n integer matrix. From each cell, you can move in four directions (up, down, left, right) to an adjacent cell with a strictly larger value. Return the length of the longest increasing path.

The brute force DFS from every cell without memoization revisits cells exponentially. The key insight is that the strict-increase constraint means the graph has no cycles — it is a Directed Acyclic Graph (DAG). On a DAG, longest path is solvable in linear time.

Two approaches work: DFS with memoization (compute each cell's longest path once and cache it) and BFS topological sort (peel layers from cells with no incoming edges). Both run in O(m*n) time since each cell is computed exactly once.

Create a memo table dp of size m x n, initialized to 0. For each cell (i, j), if dp[i][j] > 0 it has already been computed — return it. Otherwise, DFS to all four neighbors that have strictly larger values, recursively compute their longest paths, and set dp[i][j] = 1 + max of those results.

The base case: if no neighbor has a larger value, dp[i][j] = 1 (the cell itself). The recursion naturally handles the DAG structure because we only move to strictly larger values, guaranteeing no cycles and thus no infinite recursion.

After computing dp for all cells, return the maximum value in the dp table. This is the global longest increasing path. Each cell is computed exactly once (subsequent visits return the cached value), giving O(m*n) total time.

Build an in-degree matrix: for each cell, count how many of its 4 neighbors have strictly smaller values (these would point to this cell in the DAG). Cells with in-degree 0 are local minima — they start at layer 1.

Use BFS: enqueue all cells with in-degree 0. Process layer by layer. For each cell, decrement the in-degree of its larger neighbors. When a neighbor's in-degree reaches 0, enqueue it for the next layer. The number of layers processed is the longest path.

This is Kahn's algorithm applied to the implicit DAG formed by the matrix. Each cell is enqueued and dequeued exactly once. The total time is O(m*n) with O(m*n) space for the in-degree matrix and queue.

Consider matrix = [[9,9,4],[6,6,8],[2,1,1]]. DFS from (2,1) value 1: neighbors (1,1)=6 > 1, (2,0)=2 > 1, (2,2)=1 not >. DFS(1,1)=6: neighbors (0,1)=9 > 6, (1,0)=6 not >, (1,2)=8 > 6. DFS(0,1)=9: no larger neighbors, dp=1. DFS(1,2)=8: neighbor (0,2)=4 not >8, (0,1) not computed from here... dp(1,2)=1+max(dp neighbors).

Let me trace more carefully. DFS(0,2)=4: neighbors (0,1)=9>4 → DFS(0,1)=1, (1,2)=8>4 → DFS(1,2). DFS(1,2)=8: neighbor (0,2)=4 not >, (0,1)=9>8 → dp=1. So DFS(1,2)=2. Back to DFS(0,2): max(1,2)+1=3. DFS(1,1)=6: (0,1)=9→1, (1,2)=8→2. DFS(1,1)=3.

DFS(2,1)=1: (1,1)=6→3, (2,0)=2→?. DFS(2,0)=2: (1,0)=6→?. DFS(1,0)=6: (0,0)=9→1, (1,1)=6 not >, (0,1) not computed from here... DFS(1,0)=2. DFS(2,0)=3. DFS(2,1)=max(3,3)+1=4. Answer: 4. Path: 1→2→6→9.

Python DFS: use @lru_cache or a manual dp matrix. For each cell, check 4 neighbors. If neighbor value > current value, recurse. dp[i][j] = 1 + max(dfs(ni, nj) for valid neighbors), or 1 if no valid neighbors. Return max of all dp values.

Java DFS: int[][] dp = new int[m][n]. For each cell, if dp[i][j] != 0 return it. Otherwise recurse to valid neighbors, cache, and return. Use a directions array int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}} for clean neighbor iteration.

Python BFS topological sort: compute in-degrees, enqueue zeros, process layers counting depth. While queue: next_queue = []. For each cell in queue, for each larger neighbor, decrement in-degree; if 0, add to next_queue. Increment depth. Return depth.

Time complexity is O(m * n) for both approaches. DFS memoization: each cell is computed exactly once (O(1) amortized per cell). Topological sort: each cell is enqueued and dequeued once, each edge is traversed once.

Space complexity is O(m * n) for the memoization table (DFS) or in-degree matrix + queue (BFS). The DFS recursion stack can reach O(m * n) depth in the worst case (a spiral path), which may cause stack overflow for very large matrices. The BFS approach avoids this.

Both are optimal — we must examine every cell at least once. The DAG structure (no cycles due to strict increase) is what makes O(m * n) possible. Without the strict-increase constraint, longest path would be NP-hard.

Pacific Atlantic Water Flow (LeetCode 417) runs DFS from ocean borders inward, similar to how this problem runs DFS from each cell outward. Both use memoization on grid cells. Practice them together for comprehensive grid DFS coverage.

Shortest Bridge (LeetCode 934) combines DFS (mark island) with BFS (expand outward). Longest Increasing Path uses DFS with memoization or BFS with topological sort. Both demonstrate the power of combining DFS and BFS on grids.

Longest Increasing Subsequence (LeetCode 300) is the 1D version of this problem. The matrix version adds spatial dimensions but the core idea — find the longest strictly increasing chain — is the same. Mastering LIS first makes the matrix version more intuitive.