Longest Increasing Path in a Matrix: DFS with Memoization

Given an m x n integer matrix, return the length of the longest strictly increasing path. From each cell you can move in four directions: up, down, left, right. You cannot move diagonally, step outside the boundary, or revisit any cell.

This is LeetCode 329: Longest Increasing Path in a Matrix, and it is a hard problem that feels intimidating at first glance. Once you see the key insight, though, it becomes a clean DFS with memoization that reuses skills from Number of Islands and Longest Increasing Subsequence.

Why the naive approach is too slow

The brute force idea is to run a full DFS from every cell and track the longest path found. That works for tiny inputs, but each DFS could visit O(m * n) cells, and you run it from every cell. Worst case: O((m * n)^2). For a 200x200 grid that is 1.6 billion operations.

The expensive part is recomputation. When you DFS from cell A and pass through cell B, you compute how far you can go from B. Then when you DFS from cell C and also pass through B, you compute it all over again. Memoization eliminates that entirely.

The key insight: no cycles, so no visited set needed

For each cell, the answer is: 1 + the maximum answer among all neighbors with a strictly smaller value. This is a clean recursive definition.

Here is the crucial observation: because paths must be strictly increasing, you can never return to a cell you have already visited in the current path. If cell A has value 5 and you move to neighbor B with value 3 (smaller), you cannot later move back to A from B because A=5 is larger than B=3. The strictly increasing constraint makes cycles structurally impossible.

This means you do not need a visited set to prevent infinite loops. The recursion always terminates, because every step moves to a strictly smaller value and values are bounded below.

No cycles also means the recursion graph is a DAG (directed acyclic graph). Each node has a well-defined answer that depends only on its smaller neighbors, and those answers can be cached forever.

The DFS with memoization solution

def longestIncreasingPath(matrix: list[list[int]]) -> int:
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = {}

    def dfs(r, c):
        if (r, c) in dp:
            return dp[(r, c)]
        best = 1
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] < matrix[r][c]:
                best = max(best, 1 + dfs(nr, nc))
        dp[(r, c)] = best
        return best

    return max(dfs(r, c) for r in range(m) for c in range(n))

Walk through each piece:

The dp dict maps (row, col) to the length of the longest increasing path starting at that cell. Once a cell is computed, every future call to dfs(r, c) returns in O(1) via the cache lookup at the top.

The base case is implicit: if no neighbor has a smaller value, the loop never updates best, and best stays at 1. The cell itself is a path of length 1.

The neighbor filter matrix[nr][nc] < matrix[r][c] enforces the strictly increasing constraint. We only recurse into cells with a smaller value, so we are always moving to shorter subproblems. This is the same guard that prevents cycles.

The outer loop max(dfs(r, c) for r in range(m) for c in range(n)) starts DFS from every cell and takes the maximum. We cannot just pick one starting cell because the longest path might start anywhere.

Visual walkthrough

Here is how the memoization cache fills up as DFS explores the path 1 to 2 to 6 to 9 in the example grid.

Notice how each DFS call uses the already-cached answer for cells it depends on. Cell (0,0)=9 does not re-explore the path through 6, 2, and 1. It just reads dp[(1,0)]=3 from the cache and adds 1.

Complexity analysis

Time is O(m * n). Each cell's dfs runs exactly once; every subsequent call hits the cache in O(1). The four-neighbor loop inside each dfs does O(1) work per neighbor. Total work across all cells is proportional to the number of cells times the number of neighbors, which is O(4 * m * n) = O(m * n).

Space is O(m * n) for the memoization dict. The recursion stack depth is at most m * n in the worst case (a grid where the path winds through every cell). Python's default recursion limit is 1000, so for very large grids you may need sys.setrecursionlimit or an iterative approach with topological sort.

Building blocks

This problem snaps together three reusable pieces:

1. DFS on a grid

The same four-direction neighbor generation from every grid problem:

for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
    nr, nc = r + dr, c + dc
    if 0 <= nr < m and 0 <= nc < n:
        # (nr, nc) is a valid neighbor

You saw this in Number of Islands and Word Search. The only thing that changes between problems is the condition under which you recurse into a neighbor.

2. Top-down DP with memoization

The pattern: check the cache first, compute if missing, store before returning.

def dfs(r, c):
    if (r, c) in dp:
        return dp[(r, c)]
    # ... compute result ...
    dp[(r, c)] = result
    return result

This converts an exponential-time recursion into a linear-time one. It works here specifically because the recursion is acyclic: the strictly increasing constraint guarantees you never have dfs(A) depending on dfs(B) which depends back on dfs(A).

3. DAG structure from a problem constraint

The strictly increasing constraint creates a DAG implicitly. Every directed edge points from a larger cell to a smaller cell. In a DAG, you can define a well-founded recursive decomposition: the answer for any node depends only on the answers for nodes it points to. That is exactly what makes memoization safe here.

This is the same structure as Longest Increasing Subsequence, where the strictly increasing constraint on the 1D array makes the DP states acyclic. LIP in a matrix is the 2D generalization of that idea.

Edge cases

Before submitting, think through these:

• 1x1 matrix: only one cell, no neighbors. DFS returns 1 immediately. Correct.
• All same values: no cell has a strictly smaller neighbor. Every dfs returns 1. Answer is 1.
• Single row: cells can only move left or right. The algorithm handles this correctly because bounds checking filters out up/down moves.
• Single column: same idea, only up/down moves are valid.
• Already strictly increasing row/column: the longest path runs the entire row or column. The memoization collapses the recursion into a single O(n) chain.
• Strictly decreasing grid: DFS from the largest cell reaches every cell. The answer equals the total number of cells.

Why no visited set is needed

This is the question that trips up almost everyone on first read. In Number of Islands and Word Search, you need a visited set to prevent infinite loops. Why not here?

In Number of Islands, you do flood fill. You could move from A to B and then potentially back to A because there is no constraint on values. You prevent that cycle with a visited set.

In Word Search, the path must spell a specific word. A cell used in position 3 of the word cannot also be used in position 5, so you mark it visited and unmark it on backtrack.

In this problem, movement requires going to a strictly smaller value. If you go from A=5 to B=3, you cannot go back from B=3 to A=5 because 5 is not smaller than 3. The constraint itself is the cycle prevention. You get the safety of a visited set for free from the problem structure.

That is also why memoization is safe. If dfs(A) calls dfs(B) which calls dfs(C), none of those calls can loop back. By the time dfs(A) runs, dfs(B) will have finished and stored its result. There is no risk of reading a partial or recursive cache entry.

From understanding to recall

You now see the full picture: DFS from every cell, strictly increasing constraint eliminates cycles and the visited set, memoization eliminates recomputation. The result is a clean O(m * n) algorithm built from grid DFS and top-down DP.

The challenge is not understanding this. It is writing it from scratch in an interview. Can you set up the dp dict, write the four-direction loop with bounds checking, apply the strictly increasing filter, store the result before returning, and run DFS from every cell? Each of those steps is small, but forgetting any one of them breaks the solution.

Spaced repetition closes that gap. You write the grid DFS skeleton and the memoization wrapper from memory at increasing intervals. After a few rounds, the pattern is automatic. When you see "longest path in a grid with some constraint," your hand reaches for dp = {}, def dfs(r, c):, and the four-direction loop without hesitation.

Related posts

• Number of Islands - same DFS-on-a-grid skeleton, different goal
• Word Search - DFS on grid with backtracking, builds the same spatial intuition
• Longest Increasing Subsequence - the 1D version of this idea, DP on sequences

CodeBricks breaks Longest Increasing Path in a Matrix into its grid-DFS, memoization, and DAG-structure building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a memoized grid DFS problem shows up in your interview, you do not think about it. You just write it.