How do you solve Longest Increasing Path in a Matrix?

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.

What pattern does Longest Increasing Path in a Matrix use?

The Pattern: Dynamic Programming (Top-Down Memoization with DFS) The Heuristic: 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.

Longest Increasing Path in a Matrix

Q: What is the time complexity of Longest Increasing Path in a Matrix?

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.

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

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

Output: 4

Starting 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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Solution

Python

1class Solution:
  def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
      ROWS, COLS = len(matrix), len(matrix[0])
      memo = {}
5
      def dp(r, c, prev_val):
          if (r < 0 or r == ROWS or
              c < 0 or c == COLS or
              matrix[r][c] <= prev_val):
              return 0
          if (r, c) in memo:
              return memo[(r, c)]
          
          res = 1
          res = max(res, 1 + dp(r + 1, c, matrix[r][c]))
          res = max(res, 1 + dp(r - 1, c, matrix[r][c]))
          res = max(res, 1 + dp(r, c + 1, matrix[r][c]))
          res = max(res, 1 + dp(r, c - 1, matrix[r][c]))
          memo[(r, c)] = res
          return res
21
      max_path = 0
      for r in range(ROWS):
          for c in range(COLS):
              max_path = max(max_path, dp(r, c, -1))
      
      return max_path

Step-by-Step Solution

1

Compute Longest Increasing Path from Each Cell Using Memoized DFS

6def dp(r, c, prev_val):
  if (r < 0 or r == ROWS or
      c < 0 or c == COLS or
      matrix[r][c] <= prev_val):
      return 0
  if (r, c) in memo:
      return memo[(r, c)]
  res = 1
  res = max(res, 1 + dp(r + 1, c, matrix[r][c]))
  res = max(res, 1 + dp(r - 1, c, matrix[r][c]))
  res = max(res, 1 + dp(r, c + 1, matrix[r][c]))
  res = max(res, 1 + dp(r, c - 1, matrix[r][c]))
  memo[(r, c)] = res
  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.

2

Iterate Over All Cells to Find the Global Longest Increasing Path

To evaluate the longest increasing path starting from every cell and track the maximum length found.

3

Return the Length of the Longest Increasing Path Found

To output the maximum length of any strictly increasing path discovered in the matrix.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 11 Critical

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.

Line 4 Critical

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.

Line 12 Critical

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.

Full line-by-line criticality + rationale for all 21 lines available on Pro.

Test Your Understanding

Why does memoization prevent the exponential blowup in this DFS approach?

See the answer with Pro.

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

or drill a free problem

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`

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`