Longest Increasing Path in a Matrix
Understanding the Problem
We have a 2D grid of integers, and we need to find the longest path where each step moves to a strictly larger value. Movement is restricted to the four cardinal directions (up, down, left, right), no diagonals.
The path must be strictly increasing, so it can never revisit a cell: a cell's value cannot be strictly greater than itself. That eliminates cycles. The implicit graph formed by "cell A has an edge to cell B if B is an adjacent cell with a larger value" is a Directed Acyclic Graph (DAG), and finding the longest path in a DAG can be solved with dynamic programming or a topological ordering.
The path can also start and end at any cell, so every cell is a potential starting point and the answer is the maximum over all of them.
Key Constraints:
1 <= m, n <= 200-> The matrix has at most 40,000 cells, so an O(m * n) solution runs well within limits.0 <= matrix[i][j] <= 2^31 - 1-> Values reach the top of the signed 32-bit range. The code only compares values, never sums them, so a 32-bitintis safe and there is no overflow risk.- Strictly increasing -> No cycles in the movement graph, which is what makes the DP and topological approaches valid.
Approach 1: Brute Force DFS
Intuition
Try every cell as a starting point and explore all increasing paths from it with DFS. From a cell, look at all four neighbors and recurse into any neighbor with a strictly larger value. The longest path starting from a cell is 1 (the cell itself) plus the maximum path length among its valid neighbors.
Without caching, the same subproblems get recomputed repeatedly. If cell (0, 0) leads to cell (1, 0), and cell (0, 1) also leads to cell (1, 0), the entire subtree rooted at (1, 0) is explored twice. In the worst case this is exponential.
Algorithm
- For each cell (i, j) in the matrix, run a DFS to find the longest increasing path starting from that cell.
- In the DFS, explore all four directions. For each neighbor with a strictly larger value, recursively compute the path length.
- Return 1 + max of all valid neighbor path lengths.
- Track the global maximum across all starting cells.
Example Walkthrough
Code
- Time Complexity: O(4^(m*n)). Without memoization, each cell can branch into up to 4 directions. The same cells get explored exponentially many times through different paths.
- Space Complexity: O(m n). The recursion stack can go as deep as the longest path, which in the worst case is m n.
The brute force recomputes the same cell's longest path every time it is reached from a different predecessor. The next approach computes each cell's result once and caches it.
Approach 2: DFS with Memoization
Intuition
The brute force recomputes paths from cells it has already fully explored, so add a cache. Define dp[i][j] as the length of the longest increasing path starting from cell (i, j). The first time DFS computes it, store the value. Every future call for the same cell returns the cached value in O(1).
With memoization, each cell is computed once. The DFS from a cell visits at most 4 neighbors, and each neighbor either returns a cached value or triggers a computation that happens only once. The total work across all DFS calls is O(m * n).
Memoization is only safe when a subproblem's answer does not depend on the path taken to reach it. Here dp[i][j] depends solely on the values of (i, j) and its larger neighbors, never on the caller. The strictly increasing constraint also guarantees the recursion has no cycles: a value cannot increase along a path and return to an earlier cell. So every DFS terminates and the cached value for a cell is the same no matter which cell requested it.
Algorithm
- Create a 2D array
dpof size m x n, initialized to 0 (0 means "not yet computed"). - For each cell (i, j), call dfs(i, j).
- In dfs(i, j): if dp[i][j] is already computed (non-zero), return it. Otherwise, explore all four neighbors with strictly larger values, recursively compute their path lengths, and set dp[i][j] = 1 + max of all valid neighbor results.
- Return the maximum value in
dp.
Example Walkthrough
Code
- Time Complexity: O(m n). Each cell is visited and computed exactly once. Each computation checks at most 4 neighbors. Total: O(4 m n) = O(m n).
- Space Complexity: O(m n). The dp array takes O(m n). The recursion stack in the worst case can go O(m * n) deep if the entire grid forms one long increasing path.
The DFS with memoization is optimal in time, but its recursion stack can be as deep as m * n, which risks a stack overflow on a 200 x 200 grid that forms one long path. The next approach processes cells iteratively using a topological ordering, avoiding deep recursion.
Approach 3: BFS Topological Sort (Peeling)
Intuition
Instead of DFS, use BFS with a topological ordering (Kahn's algorithm). Define each cell's in-degree as the count of adjacent cells with strictly smaller values. Cells with in-degree 0 are local minima and form the first BFS layer. Process layer by layer: for each processed cell, decrement the in-degree of every larger neighbor, and when a neighbor's in-degree reaches 0, add it to the next layer. The number of layers processed equals the longest increasing path.
A cell's in-degree counts the smaller neighbors that can step into it, so a cell only reaches in-degree 0 after every smaller neighbor has been processed. Processing in layers therefore visits a cell exactly when the longest increasing path ending at it is fully determined. The layer index a cell lands in is the length of the longest path ending there, and the total layer count is the length of the longest path in the whole grid.
Algorithm
- Compute the in-degree of each cell. A cell's in-degree is the number of adjacent cells with a strictly smaller value.
- Add all cells with in-degree 0 to the BFS queue (these are local minima).
- Process the BFS level by level. For each cell in the current level, check all four neighbors. If a neighbor has a strictly larger value, decrement its in-degree. If it drops to 0, add it to the next level.
- Count the number of BFS levels processed. That is the answer.
Example Walkthrough
Code
- Time Complexity: O(m n). Computing in-degrees takes O(m n). The BFS processes each cell exactly once and each edge at most once. Total edges are at most 4 m n. Overall O(m * n).
- Space Complexity: O(m n). The in-degree array takes O(m n). The BFS queue can hold at most O(m * n) cells.