← DSA Atlas
Dedicated problem page · #329

Longest Increasing Path in a Matrix

HardTopological SortLongest path in an implicit DAG via memoized DFSDFS with memoization over an increasing-value DAG
Solve on LeetCode ↗
329
HardTopological SortDFS with memoization over an increasing-value DAGLongest path in an implicit DAG via memoized DFS

Longest Increasing Path in a Matrix

Given an m x n integer matrix, return the length of the longest strictly increasing path. From any cell you may move up, down, left, or right (no diagonals, no wraparound), and each step must go to a strictly greater value.

Open official problem prompt ↗
In plain English

Compute the length of the longest strictly increasing walk through the grid using only orthogonal steps.

Picture it like this

Water flows only downhill; here you climb only uphill, and you want the longest uninterrupted climb starting anywhere on the terrain.

Example
Input
matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
Output
4
Why
The path 1 -> 2 -> 6 -> 9 increases at every step and has length 4.
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1
Pattern lesson

See the pattern, then code

Longest path in an implicit DAG via memoized DFS
Recognition clue

You need the longest chain under a strict-increase move rule; because moves only go to larger values there are no cycles, so it is a longest-path query on a DAG, solvable by memoized DFS.

↗
Topological Sort

Prerequisites, dependencies, build order, or scheduling over a DAG.. Strictly increasing edges make the grid a DAG, so the longest path starting at a cell depends only on the cell, not the route taken to reach it. Cache each cell's answer to avoid recomputation.

New words, made simpleKnow these before the algorithm
Implicit DAG
The graph whose edges connect a cell to strictly-greater neighbors; strict increase guarantees acyclicity.
Memoization
Caching dfs(r, c) so each cell's longest-path length is computed a single time.
Longest path
In a DAG this is polynomial (unlike general graphs) via DP over topological order.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Plain DFS from every cell

Recomputes overlapping subpaths repeatedly; too slow.

Explore all increasing paths from each start with no caching.

Time Exponential in the worst caseSpace O(m * n) recursion
Best choiceMemoized DFS (top-down DAG DP)

Each cell computed once; optimal and simple.

Cache each cell's longest increasing path; neighbors are only larger cells so recursion terminates.

Time O(m * n)Space O(m * n)
The rule we keep true

Invariant

Once dfs(r, c) returns, its cached value is the exact longest increasing path length starting at (r, c) and never changes.

Why this is correct

Reasoning

Because every edge points from a smaller to a strictly larger value, no cell can appear twice on one path, so the recursion has no cycles and always terminates. The value at a cell depends only on strictly larger neighbors, which form independent subproblems, so caching gives a correct linear DP.

The algorithm in three movesSay these aloud before coding
1Define dfs(r, c) = longest increasing path starting at cell (r, c)

dfs(2,1)=1 for value 1

2For each of the four neighbors with a strictly greater value, recurse and take 1 + the best neighbor result

dfs at 2->6->9 chains to 4

3Memoize dfs(r, c) so each cell is computed once

answer = max over cells = 4

4Return the maximum of dfs over all cells

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
90
91
42
63
64
85
26
17
18
1 · Readcell (2,1)=1
2 · AskLarger neighbors?
3 · Update stateup is 6, and (2,0)=2
4 · Resultdfs explores both branches.
Key takeaway

The increasing chain 1 (bottom) -> 2 -> 6 -> 9 spans four cells for length 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-5Guards and dimensions

    Empty matrix returns 0; capture rows and cols for bounds checks.

  2. 2
    Lines 7-15Memoized DFS core

    lru_cache stores each cell result; only strictly-greater neighbors extend the path.

  3. 3
    Lines 16Aggregate over starts

    The answer is the best path length starting from any cell.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • 1 x 1 matrix -> 1
  • All equal values -> no strict increase, every cell answers 1
  • Strictly increasing single row or column -> length equals that dimension
  • Large 200 x 200 grid -> still linear in cells
!

Common beginner mistakes

  • Allowing >= moves instead of strict >, which creates cycles and wrong lengths
  • Forgetting to memoize, causing exponential blowup
  • Counting steps (edges) instead of cells, returning length - 1
  • Adding diagonal moves that the problem does not permit
Check your understanding

Why is longest path solvable in polynomial time here when it is NP-hard on general graphs?

More in Topological Sort

#207Course ScheduleCycle detection by peeling zero in-degree nodes#210Course Schedule IIEmit nodes in dependency-safe order#269Alien DictionaryDerive edges from adjacent-item comparisons, then topologically sort#310Minimum Height TreesTrim leaves inward until the center remains#1203Sort Items by Groups Respecting DependenciesTwo-level topological sort (order groups, then items within groups)#2050Parallel Courses IIITopological longest path (critical path)