Longest Increasing Path in a Matrix — Solution

Problem

Given an integer matrix, find the length of the longest path where each successive cell's value is strictly greater than the previous one. From any cell you can move up, down, left, or right — not diagonally, and never off the edge of the board.

• Input: matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
• Output: 4
• Explanation: The path 1 → 2 → 6 → 9 visits four cells, each strictly greater than the last.

Intuition

Because every step must increase in value, you can never revisit a cell on the same path — the movement graph is a directed acyclic graph (DAG). This means the longest increasing path starting from any cell can be computed once and reused: if two different paths both pass through cell (r, c), they can share the same cached answer for that cell. Memoized DFS converts what would otherwise be an exponential search into a single linear pass over the grid.

Solution — Memoized DFS

For each cell, recursively explore all four neighbors that hold a strictly larger value and take the maximum depth found. Store each result so that revisiting a cell returns the cached value instantly.

1. Initialize a memo table of the same dimensions, all set to 0 (uncomputed).
2. For every cell in the matrix, call dfs(r, c).
3. In dfs(r, c): set best = 1 (the cell itself), then for each direction check that the neighbor is in bounds and strictly greater.
4. For each valid neighbor, extend the path: best = max(best, 1 + dfs(neighbor)).
5. Store memo[r][c] = best and return it; track the global maximum across all starting cells.

1def longestIncreasingPath(matrix: list[list[int]]) -> int:
2    rows, cols = len(matrix), len(matrix[0])
3    memo = {}  # maps (row, col) to the longest increasing path starting there
4
5    def dfs(row, col):
6        if (row, col) in memo:
7            return memo[(row, col)]
8
9        best = 1  # every cell is a valid path of length 1 by itself
10        for delta_row, delta_col in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
11            neighbor_row = row + delta_row
12            neighbor_col = col + delta_col
13            if (0 <= neighbor_row < rows
14                    and 0 <= neighbor_col < cols
15                    and matrix[neighbor_row][neighbor_col] > matrix[row][col]):
16                best = max(best, 1 + dfs(neighbor_row, neighbor_col))
17
18        memo[(row, col)] = best
19        return best
20
21    return max(dfs(r, c) for r in range(rows) for c in range(cols))

Time: O(m × n) — each cell is computed exactly once; all subsequent calls to that cell return the cached value in O(1).
Space: O(m × n) — for the memo table; recursion depth is bounded by m × n in the worst case.

Complexity Summary

Common Mistakes

• Allowing equal neighbors — the path must be strictly increasing; using >= instead of > when comparing neighbors incorrectly includes equal-value steps and overstates the path length.
• Using a visited set during DFS — unlike cycle-detection DFS, you should not block cells with a visited flag. The same cell can anchor paths that arrive from many different directions; blocking it cuts off valid routes.
• Initializing best to 0 instead of 1 — the current cell always contributes 1 to the path length; starting from 0 understates every result by one.
• Combining bound checks with or — a neighbor is valid only when all four conditions hold simultaneously; using or between any pair admits out-of-range indices and causes an index error.
• Skipping memoization and running plain DFS from every cell — without caching, the same subproblems are recomputed for every path that passes through a shared cell, producing exponential runtime on dense grids.

Related Problems

• word-search — DFS on a 2D grid to find a word; same four-directional movement, but uses backtracking instead of memoization.
• number-of-islands — DFS/BFS to identify connected components in a matrix.
• 01-matrix — BFS from multiple sources to compute shortest distances to the nearest zero.
• max-area-of-island — DFS to measure the size of each connected land region.
• path-with-maximum-gold — DFS with backtracking to maximize the total value collected along a path in a matrix.