Longest Increasing Path in a Matrix

Explanation & Solution

Description

Given an m x n integers matrix, return the length of the longest increasing path in the matrix.

From each cell, you can move in four directions: up, down, left, or right. You may not move diagonally or move outside the boundary of the matrix. You may not revisit cells within the same path.

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output: 4

Explanation: The longest increasing path is [1, 2, 6, 9].

Constraints

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

Approach

Topological Sort pattern

1. Set Up Memoization

Create a memo matrix of the same dimensions, initialized to 0.
memo[r][c] will store the length of the longest increasing path starting from cell (r, c).
Define the four movement directions: up, down, left, right.

2. Define the DFS Function

For cell (r, c), if memo[r][c] is already computed (non-zero), return it immediately.
Otherwise, initialize maxLen = 1 (the cell itself counts as a path of length 1).
Explore all four neighbors (nr, nc).

3. Explore Valid Neighbors

A neighbor is valid if it is within bounds and its value is strictly greater than the current cell.
For each valid neighbor, recursively compute the longest increasing path from that neighbor.
Update maxLen = max(maxLen, 1 + dfs(nr, nc)).

4. Cache and Return

Store maxLen in memo[r][c] so future calls to the same cell return instantly.
Return maxLen.

5. Find the Global Maximum

Iterate over every cell in the matrix.
Call dfs(r, c) for each cell and track the overall maximum.
Return the global maximum as the answer.

Key Insight

The strictly increasing constraint guarantees no cycles, which means the dependency graph is a DAG (Directed Acyclic Graph). This makes DFS with memoization safe and equivalent to a topological sort approach. Each cell is computed at most once, so the total work is bounded.

Time

O(m * n)each cell is visited and computed exactly once due to memoization.

Space

O(m * n)for the memo table and recursion stack in the worst case.

Visualization

Input:

DFS Traversal3×3 grid

output—

Press play to start dfs traversal

CurrentQueuedVisitedSource

57 steps

Solution Code

Minimum Height Trees

Sequence Reconstruction