Longest increasing path in a matrix: DFS memoization on increasing edges

Coding Challenges
1

Problem. Return the length of the longest strictly increasing path in a matrix, moving in four directions.

This is the classic memoized DAG search on grid states pattern.

Examples:

  • matrix = [[9,9,4],[6,6,8],[2,1,1]] → 4
  • matrix = [[3,4,5],[3,2,6],[2,2,1]] → 4
  • matrix = [[1]] → 1

Solution. From each cell, the next step can go only to a larger neighbor, which creates an acyclic dependency if you orient edges from smaller to larger values. DFS with memoization computes each cell’s best path once.

def longest_increasing_path(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    memo = {}

    def dfs(row, col):
        if (row, col) in memo:
            return memo[(row, col)]

        best = 1
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = row + dr
            nc = col + dc
            if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[row][col]:
                best = max(best, 1 + dfs(nr, nc))

        memo[(row, col)] = best
        return best

    return max(dfs(row, col) for row in range(rows) for col in range(cols))

O(mn) time with memoization because each cell is solved once, O(mn) memo space.

Gotchas.

  • “Increasing” means strictly larger, not larger-or-equal.
  • Without memoization, many subpaths are recomputed exponentially often.
  • You can start from any cell, so take the maximum over all starting positions.

Run: Longest Increasing Path In A Matrix