Longest Increasing Path in a Matrix

Find the longest path that moves to a larger neighboring value each step.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Longest Increasing Path in a Matrix: Treat larger-neighbor moves as a DAG, recursively solve each cell once, and memoize the longest suffix length returned to its predecessors.

Input and goalFind the longest path that moves to a larger neighboring value each step.

Start DFS at value 3The outer max begins at (0,0)=3. Only larger neighbor 4 can extend this path.

3DFS cursor45216

memo[.,.,.; .,.,.]dependency3 -> 4bestpath_from(3) starts at 1

Recognize it

Use memoized DFS when every cell asks for an optimal path through neighboring states and a strict monotone move rule prevents cycles.

Keep true

Once path_from(r,c) returns, its memo value is the longest increasing path starting at that cell; every candidate is 1 plus an already correct recursively computed larger-neighbor suffix.

Reuse it

A strict ranking function can turn implicit neighbor moves into a DAG; memoize the optimal suffix at each state and combine it from higher-ranked neighbors.

Pattern: DFS plus memoization.

Simple idea: The longest path from one cell never changes. Cache it. Larger-only moves also prevent cycles.

from functools import cache

def longest_increasing_path(matrix: list[list[int]]) -> int:
   if not matrix or not matrix[0]:
      return 0

   @cache
   def path_from(row: int, col: int) -> int:
      best = 1
      for row_step, col_step in ((1, 0), (-1, 0), (0, 1), (0, -1)):
         new_row = row + row_step
         new_col = col + col_step
         if 0 <= new_row < len(matrix) and 0 <= new_col < len(matrix[0]):
            if matrix[new_row][new_col] > matrix[row][col]:
               best = max(best, 1 + path_from(new_row, new_col))
      return best

   return max(
      path_from(row, col)
      for row in range(len(matrix))
      for col in range(len(matrix[0]))
   )

Cost: $O(rows\times cols)$ time and space.