Longest Increasing Path in a Matrix
On this page
Problem statement
Given an
R × Cgrid of integers, return the length of the longest path in which each step moves up, down, left or right to a strictly larger value. The length counts cells. Diagonal moves and wrapping around the edges are not allowed; the path may start anywhere.
A grid search that looks like it needs backtracking, but doesn't: because every step goes strictly uphill, a path can never come back to a cell, so each cell's answer can be computed once and reused. That makes it a DP on a directed acyclic graph, solvable by memoised DFS or by topological sort. Original problem: LeetCode 329.
Example

Input: [[3, 4, 5],
[2, 1, 6],
[9, 8, 7]]
Output: 9 # 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Input: [[7, 7],
[7, 7]]
Output: 1 # equal values don't count as increasing
Constraints (assumed)
- 1 ≤ R, C ≤ 200.
- 0 ≤ grid[r][c] ≤ 2³¹ − 1.
What this question tests
- Noticing that "strictly increasing" makes the move graph acyclic, so no visited set is needed.
- Memoised DFS (top-down DP) over grid cells.
- The equivalent topological sort view: peel the grid layer by layer from the local maxima.
Questions to ask first
- Strictly increasing, or non-decreasing? Equal neighbours would create cycles and change the problem. (Here: strictly.)
- Four directions or eight? (Here: four.)
- Length in cells or in moves? (Here: cells, so a single cell has length 1.)
- Do you need the path or only its length? (Here: the length.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.