Longest Increasing Path in a Matrix

Table of Contents +

Longest Increasing Path in a Matrix mixes two ideas. You walk a grid, and you remember answers as you go. The interviewer wants to see if you can run depth first search on a grid, then speed it up by saving results. That blend of search plus memory is the whole point here.

🎯 The Problem

You get a grid of numbers and you return the length of the longest increasing path.

From any cell you can move up, down, left, or right.
You can only step to a neighbor with a strictly larger value.
You cannot move diagonally.
A path’s length is the count of cells it visits.

Let us say the grid is:

Input:  matrix =
  9  9  4
  6  6  8
  2  1  1

Output: 4

Explanation: The longest increasing path is 1 -> 2 -> 6 -> 9.
Each step moves to a strictly larger neighbor, so its length is 4.

You can never step onto an equal or smaller value. So every path keeps rising.

Here is the grid with the best path drawn as arrows. Each arrow goes to a larger neighbor.

🐢 Approach 1: Plain DFS From Every Cell (Brute Force)

Run a depth first search from every cell and keep the longest path.

The idea:

DFS means you go as deep as you can down one path before backing up.
Start at a cell, look at its four neighbors, step into any that is strictly larger.
From there, do the same again, keeping a running length.

How it works:

The best length over all starting cells is the answer.
No “visited” set is needed here.
Strictly rising values mean you can never loop back, so a cycle is impossible.

Why it is weak:

The same cell gets explored again and again from different starting paths.
The work explodes, close to exponential in the worst case.
Far too slow for a big grid.

Here is the plain DFS code:

def longest_increasing_path(matrix):
    rows, cols = len(matrix), len(matrix[0])

    def dfs(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 < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + dfs(nr, nc))
        return best

    return max(dfs(r, c) for r in range(rows) for c in range(cols))

🚀 Approach 2: DFS With Memoization (Best)

Save each cell’s answer the first time you compute it.

The idea:

The longest increasing path starting at a cell never changes.
It does not matter how you arrived there. The answer from (row, col) is fixed.

How it works:

Keep a second grid called memo.
memo[r][c] holds the longest increasing path that starts at cell (r, c).
Look at each larger neighbor, ask for its stored answer, take the biggest, add one.
A cell with no larger neighbor has answer one.
The grand answer is the largest value across the whole memo grid.

Why it is fast:

Memoization means each cell is computed only once, then read back.
From each cell you check four neighbors.
Time is O(rows × cols).

Steps to Solve

Make a memo grid the same size as the matrix, all zeros. Zero means “not computed yet”.
Write a dfs(r, c) that returns the longest increasing path starting at (r, c).
Inside dfs, if memo[r][c] is not zero, return it right away.
Start best at 1, for the cell itself.
For each of the four neighbors that is strictly larger, set best to the larger of best and 1 + dfs(neighbor).
Store best in memo[r][c] and return it.
Call dfs from every cell and keep the largest result.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a nested dfs function and a memo grid of zeros.

def longest_increasing_path(grid):
    rows, cols = len(grid), len(grid[0])
    memo = [[0] * cols for _ in range(rows)]   # 0 means not computed yet

    def dfs(r, c):
        if memo[r][c] != 0:        # already solved this cell
            return memo[r][c]
        best = 1                   # the cell itself counts as length 1
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c]:
                best = max(best, 1 + dfs(nr, nc))   # extend into larger neighbor
        memo[r][c] = best          # store before returning
        return best

    answer = 0
    for r in range(rows):
        for c in range(cols):
            answer = max(answer, dfs(r, c))
    return answer


grid = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
print(longest_increasing_path(grid))

The output of the above code will be:

Let us walk through the Python version line by line. The memo grid is what makes it fast.

rows, cols = len(grid), len(grid[0])
memo = [[0] * cols for _ in range(rows)]

We read the grid size. Then we build a memo grid of the same shape, full of zeros. A zero means “I have not solved this cell yet”. So memo[r][c] will later hold the longest path starting at that cell.

def dfs(r, c):
    if memo[r][c] != 0:
        return memo[r][c]

This is the heart. If we already solved this cell, we return the saved answer at once. This line is what turns the slow search into a fast one. No cell is ever computed twice.

    best = 1

Every cell is a path of length one by itself. So we start best at one.

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

We try the four neighbors: up, down, left, right. We keep a neighbor only if it sits inside the grid and holds a strictly larger value. For each valid neighbor we ask for its own longest path with dfs(nr, nc). We add one for the step into it. We keep the largest answer in best.

    memo[r][c] = best
    return best

Before returning we store best in the memo grid. Next time anyone asks about this cell, the answer is ready.

answer = 0
for r in range(rows):
    for c in range(cols):
        answer = max(answer, dfs(r, c))
return answer

We start the search from every cell. The longest path may begin anywhere. We keep the biggest result across all starts.

Here is how the memo grid fills in for our example. Cells with no larger neighbor get one first. Then taller paths build on top of them.

⏱️ Time and Space Complexity

Plain DFS revisits cells over and over, so it is close to exponential. With memoization each cell is solved once. From each cell we check four neighbors. So the work is O(rows * cols). The memo grid and the recursion stack each use O(rows * cols) space. Here the grid has rows times cols cells.

Approach	Time Complexity	Space Complexity
Plain DFS from every cell	Exponential (worst case)	O(rows * cols)
DFS with memoization	O(rows * cols)	O(rows * cols)

Tip

You do not need a visited set here. Because every move must go to a strictly larger value, you can never revisit a cell on the same path. That rising rule keeps the search free of cycles, which is what lets memoization work.

🧩 Key Takeaways

✅ Run DFS from every cell, moving only to strictly larger neighbors.
✅ The longest path from a cell is fixed, so store it in a memo grid.
✅ A zero in the memo grid means “not solved yet”; any other number is the saved answer.
✅ No visited set is needed, because strictly increasing values cannot form a cycle.
✅ Memoization turns an exponential search into O(rows * cols) time.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Target Sum
Interleaving String

Previous Interleaving String Next Distinct Subsequences

Longest Increasing Path in a Matrix

Follow Us

Follow Us