Problem Statement

Longest Increasing Path in a Matrix

You are given a grid of numbers with m rows and n columns. Starting from any cell, you can step to a neighbor that is directly up, down, left, or right, but only if that neighbor holds a strictly larger number. You want the longest chain of steps you can make where each number is bigger than the one before. The answer is the length of that longest chain. The tool we use here is DFS with memoization. DFS, short for depth first search, means: from a cell, walk as far as you can in one direction following the rules, and when you get stuck, back up and try another direction. Memoization means: once you figure out an answer for a cell, write it down so you never have to compute it again. Think of it like a study group where each person solves one question and posts the answer on the wall, so nobody redoes the same work. Here is the key idea: the longest increasing path that starts at a cell depends only on its larger neighbors. And because you can only move to strictly larger values, you can never walk in a circle and come back to where you started. No circles means no cycles, which means memoization is safe and each cell's answer is stable.

hardGraphDFSDynamic ProgrammingDynamic ProgrammingTime: O(m*n) · Space: O(m*n)

Signals to notice

longest increasing path in matrix4-directional movesDFS + memoization

Brute force first

DFS from each cell without caching — exponential.

The key insight

DFS with memo: dp[i][j] = longest path from (i,j). Try 4 neighbors with strictly larger values. Cache results. O(m×n).

Trace it on `matrix=[[9,9,4],[6,6,8],[2,1,1]] (3x3)`

dfs(2,1) val=1: neighbors larger than 1 are up(1,1)=6 -> 1+dfs(1,1), and left(2,0)=2 -> 1+dfs(2,0); right(2,2)=1 not >1. Recurse to fill memo.
dfs(2,0) val=2: up(1,0)=6>2 -> 1+dfs(1,0). dfs(1,0) val=6: up(0,0)=9>6 -> 1+dfs(0,0)=1+1=2 => memo[1][0]=2. So memo[2][0]=1+2=3.
dfs(1,1) val=6: up(0,1)=9>6 -> 1+dfs(0,1)=1+1=2; right(1,2)=8>6 -> 1+dfs(1,2). dfs(1,2) val=8: up(0,2)=4 not>8 => memo[1][2]=1. So dfs(1,1)=max(2, 1+1)=2 => memo[1][1]=2.
Back at dfs(2,1) val=1: best=max(1, 1+dfs(2,0)=4, 1+dfs(1,1)=3)=4 => memo[2][1]=4. Path 1->2->6->9.
Remaining cells: dfs(2,2) val=1: down/right OOB, up(1,2)=8>1 -> 1+dfs(1,2)=1+1=2 => memo[2][2]=2. dfs(0,0)=1, dfs(0,1)=1 (no larger neighbor). dfs(0,2) val=4: left(0,1)=9>4 -> 1+dfs(0,1)=2, down(1,2)=8>4 -> 1+dfs(1,2)=2 => memo[0][2]=2.
result = max over all dfs = 4 (from cell (2,1)).
return 4

What must stay true

Strictly increasing values guarantee no cycles — memoization is safe without a visited set. Each cell computed once.

Shape of the loop

function dfs(r, c):
    if memo[r][c]: return memo[r][c]
    best = 1
    for each (nr,nc) of 4 neighbors with matrix[nr][nc] > matrix[r][c]:
        best = max(best, 1 + dfs(nr, nc))
    memo[r][c] = best; return best
return max(dfs(r,c) for all cells)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Using a visited set — unnecessary and wrong for memoization. The same cell can be part of many paths.

Dynamic Programming Pattern