Longest Increasing Path in a Matrix
Problem
Given an m x n integer matrix, return the length of the longest strictly increasing path in the matrix. From each cell, you can move in four directions (up, down, left, right) to a cell with a strictly greater value.
- m == matrix.length
- n == matrix[i].length
- 1 ≤ m, n ≤ 200
- 0 ≤ matrix[i][j] ≤ 2³¹ - 1
Example
matrix = [[9,9,4],[6,6,8],[2,1,1]]4Starting at cell (2,1) with value 1, the path can move to (2,0) with value 2, then to (1,0) with value 6, and finally to (0,0) with value 9, forming the strictly increasing path [1, 2, 6, 9] of length 4. The algorithm explores all cells, recursively computing the longest increasing path starting from each cell, caching results to avoid redundant computations.
Approach
Straightforward Solution
A brute-force approach would attempt to explore all possible paths starting from every cell without caching, leading to exponential time complexity due to repeated exploration of the same subpaths.
Core Observation
The longest increasing path from any cell depends on the longest increasing paths from its neighbors with strictly greater values. This dependency forms overlapping subproblems with optimal substructure, making the problem suitable for dynamic programming with memoization.
Path to Optimal
Recognizing the overlapping subproblems, the solution uses a top-down DFS with memoization. For each cell, it recursively computes the longest increasing path by exploring neighbors with strictly greater values, caching results to avoid recomputation. This transforms the exponential brute-force into a polynomial-time solution.
Optimal Approach
Implement a recursive DFS function that, given a cell, returns the length of the longest increasing path starting there. Use a memo dictionary keyed by cell coordinates to store computed results. Iterate over all cells, invoking the DFS, and track the maximum path length found. This approach guarantees each cell is processed once, yielding O(m*n) time complexity.
Time
O(m * n)
Each cell is visited once in the DFS, and each neighbor exploration is constant time. Memoization ensures no cell is recomputed, resulting in linear time relative to the number of cells.
Space
O(m * n)
The memo dictionary stores results for each cell, requiring O(m*n) auxiliary space. The recursion stack can go as deep as O(m*n) in the worst case, but this is bounded by the number of cells.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization with DFS)
When a problem involves exploring paths with overlapping subproblems and optimal substructure, use DFS combined with memoization to cache intermediate results and avoid redundant computations.
Solution
| 1 | class Solution:
|
| 2 | def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
|
| 3 | ROWS, COLS = len(matrix), len(matrix[0])
|
| 4 | memo = {}
|
| 5 |
|
| 6 | def dp(r, c, prev_val):
|
| 7 | if (r < 0 or r == ROWS or
|
| 8 | c < 0 or c == COLS or
|
| 9 | matrix[r][c] <= prev_val):
|
| 10 | return 0
|
| 11 | if (r, c) in memo:
|
| 12 | return memo[(r, c)]
|
| 13 |
|
| 14 | res = 1
|
| 15 | res = max(res, 1 + dp(r + 1, c, matrix[r][c]))
|
| 16 | res = max(res, 1 + dp(r - 1, c, matrix[r][c]))
|
| 17 | res = max(res, 1 + dp(r, c + 1, matrix[r][c]))
|
| 18 | res = max(res, 1 + dp(r, c - 1, matrix[r][c]))
|
| 19 | memo[(r, c)] = res
|
| 20 | return res
|
| 21 |
|
| 22 | max_path = 0
|
| 23 | for r in range(ROWS):
|
| 24 | for c in range(COLS):
|
| 25 | max_path = max(max_path, dp(r, c, -1))
|
| 26 |
|
| 27 | return max_path |
Step-by-Step Solution
Compute Longest Increasing Path from Each Cell Using Memoized DFS
| 6 | def dp(r, c, prev_val):
|
| 7 | if (r < 0 or r == ROWS or
|
| 8 | c < 0 or c == COLS or
|
| 9 | matrix[r][c] <= prev_val):
|
| 10 | return 0
|
| 11 | if (r, c) in memo:
|
| 12 | return memo[(r, c)]
|
| 14 | res = 1
|
| 15 | res = max(res, 1 + dp(r + 1, c, matrix[r][c]))
|
| 16 | res = max(res, 1 + dp(r - 1, c, matrix[r][c]))
|
| 17 | res = max(res, 1 + dp(r, c + 1, matrix[r][c]))
|
| 18 | res = max(res, 1 + dp(r, c - 1, matrix[r][c]))
|
| 19 | memo[(r, c)] = res
|
| 20 | return res
|
Objective
To recursively compute and cache the longest strictly increasing path starting from a given cell.
Key Insight
The DFS explores all four directions from the current cell, only moving to neighbors with strictly greater values to maintain the increasing property. Memoization ensures that once the longest path from a cell is computed, it is reused, preventing redundant work. This approach leverages the problem's optimal substructure and overlapping subproblems, transforming an exponential search into a polynomial-time solution.
Interview Quick-Check
Core Logic
The DFS function returns the longest increasing path starting at a cell by recursively exploring neighbors with strictly greater values and caching results to avoid recomputation.
State & Boundaries
The base case returns 0 when the cell is out of bounds or the neighbor's value is not strictly greater, ensuring only valid increasing paths are considered.
Common Pitfalls & Bugs
Failing to memoize results leads to exponential time due to repeated exploration of the same subproblems.
Complexity
Memoization reduces the time complexity from exponential to O(m*n), as each cell's longest path is computed once.
Iterate Over All Cells to Find the Global Longest Increasing Path
| 22 | max_path = 0
|
| 23 | for r in range(ROWS):
|
| 24 | for c in range(COLS):
|
| 25 | max_path = max(max_path, dp(r, c, -1))
|
Objective
To evaluate the longest increasing path starting from every cell and track the maximum length found.
Key Insight
Since the longest increasing path can start at any cell, the algorithm must consider all cells as potential starting points. By invoking the memoized DFS on each cell and updating the global maximum, the solution ensures the overall longest path is found. This exhaustive yet efficient approach is possible because memoization prevents redundant computations.
Interview Quick-Check
Core Logic
Iterating over all cells ensures that the longest increasing path starting anywhere in the matrix is considered.
State & Boundaries
The nested loops cover every cell exactly once, guaranteeing completeness.
Common Pitfalls & Bugs
Neglecting to update the global maximum after each DFS call can lead to incorrect results.
Complexity
The overall time complexity remains O(m*n) because each DFS call is memoized.
Return the Length of the Longest Increasing Path Found
| 27 | return max_path |
Objective
To output the maximum length of any strictly increasing path discovered in the matrix.
Key Insight
After exploring all cells and caching their longest increasing paths, the global maximum stored represents the solution. Returning this value completes the algorithm, providing the length of the longest strictly increasing path.
Interview Quick-Check
Core Logic
Returning the global maximum after all DFS computations ensures the correct final answer.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if (r, c) in memo:Check if the longest path from the current cell is already computed and cached.
This memoization check is the key optimization that prevents exponential recomputation by returning cached results for previously visited cells, ensuring each cell's longest path is computed once.
memo = {}Initialize a memoization dictionary to cache longest path lengths for each cell.
Memoization is essential to avoid redundant computations by storing results of subproblems, transforming exponential recursion into polynomial time.
return memo[(r, c)]Return the cached longest path length for the current cell.
Returning the memoized result immediately terminates redundant recursion and leverages prior computation.
memo[(r, c)] = resCache the computed longest path length for the current cell.
Storing the result in memo prevents redundant future computations and enables efficient reuse.
if (r < 0 or r == ROWS orCheck if the current cell is out of matrix bounds or violates the strictly increasing condition.
This base case prevents invalid moves and terminates recursion when the path cannot be extended, ensuring correctness.
matrix[r][c] <= prev_val):Check if the current cell's value is not strictly greater than the previous cell's value.
Enforces the strictly increasing path constraint, preventing invalid path extensions.
res = max(res, 1 + dp(r + 1, c, matrix[r][c]))Update the longest path by exploring the cell below if it has a strictly greater value.
Recursively exploring downward neighbors extends the path, and adding 1 accounts for the current cell's contribution.
res = max(res, 1 + dp(r - 1, c, matrix[r][c]))Update the longest path by exploring the cell above if it has a strictly greater value.
Exploring upward neighbors similarly extends the path, ensuring all directions are considered.
res = max(res, 1 + dp(r, c + 1, matrix[r][c]))Update the longest path by exploring the cell to the right if it has a strictly greater value.
Rightward exploration completes the four-directional search for increasing neighbors.
res = max(res, 1 + dp(r, c - 1, matrix[r][c]))Update the longest path by exploring the cell to the left if it has a strictly greater value.
Leftward exploration ensures no valid path extension is missed.
max_path = max(max_path, dp(r, c, -1))Update the global maximum with the longest path starting at the current cell.
Comparing and storing the maximum ensures the final answer reflects the longest path anywhere in the matrix.
c < 0 or c == COLS orContinue the boundary and value check for the current cell.
Completes the compound condition to validate the cell's eligibility for path extension.
return 0Return 0 when the cell is invalid or path cannot be extended.
This return value represents no further path length contribution from invalid or non-increasing moves.
return resReturn the longest increasing path length starting from the current cell.
This return propagates the computed path length up the recursion stack for aggregation.
def dp(r, c, prev_val):Define the recursive DFS function to compute longest increasing path from cell (r, c).
Encapsulating the recursive logic in a helper function allows clean state management and memoization keyed by cell coordinates.
res = 1Initialize the longest path length from the current cell as 1 (the cell itself).
The minimum path length starting at any cell is 1, representing the cell alone before exploring neighbors.
return max_pathReturn the length of the longest strictly increasing path found.
This final return outputs the solution after exhaustive exploration and memoization.
max_path = 0Initialize a variable to track the global maximum path length.
This accumulator stores the best solution found across all starting cells.
for r in range(ROWS):Iterate over each row in the matrix.
Ensures every cell is considered as a potential path start point.
for c in range(COLS):Iterate over each column in the current row.
Completes the traversal of all cells in the matrix.
ROWS, COLS = len(matrix), len(matrix[0])Store the number of rows and columns in the matrix.
Caching the dimensions avoids repeated calls to len() and simplifies boundary checks throughout the algorithm.
Test Your Understanding
Why does memoization prevent the exponential blowup in this DFS approach?
Because memoization caches the longest increasing path length for each cell after its first computation, subsequent calls for the same cell return the cached result immediately, eliminating redundant recursive calls and reducing the complexity from exponential to linear in the number of cells.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Longest Increasing Path in a Matrix from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Longest Increasing Path in a Matrix drill