The problem
In a grid of numbers, find the length of the longest strictly increasing path, moving up, down, left or right.
Input: 9,9,4 / 6,6,8 / 2,1,1 Output: 4 (1 → 2 → 6 → 9)
Picture it
Picture a terrain map and a hiker who only walks uphill. For each square we ask: “what is the longest uphill hike that starts here?” It is 1 + the best answer among its higher neighbours. We remember (memoise) each square’s answer so no square is worked out twice.
How to recognise it
- You search for the longest path in a grid, moving in four directions.
- A rule such as strictly increasing means you can never return to a cell, so the paths form a graph without cycles.
- The longest path starting at a cell depends only on the longest paths starting at its higher neighbours.
- That sub-answer is the same no matter how you arrived, so it can be saved and reused.
- Grids up to 200 × 200 (40,000 cells) rule out walking every path.
Start with brute force
From every cell, walk to every higher neighbour recursively and keep the longest chain.
def lip_brute(h):
R, C = len(h), len(h[0])
def go(r, c):
best = 1
for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C and h[nr][nc] > h[r][c]:
best = max(best, 1 + go(nr, nc))
return best
return max(go(r, c) for r in range(R) for c in range(C))
On a grid where the value is row + column, every cell can step right or down, and the number of calls grows like a binomial coefficient: about 5 × 10^11 calls for 20 × 20, and about 10^120 for 200 × 200. Space is O(depth).
From brute force to the idea
- Find the waste. The chain that starts at a cell does not depend on how you reached it. Yet the brute force recomputes it for every path that passes through the cell.
- Define the sub-answer.
climb(r, c)is the length of the longest increasing path that starts at (r, c). It is 1 plus the bestclimbamong higher neighbours, or just 1 when none is higher. - Save it. The dictionary
memostores each result, so a cell is solved once and later visits are a lookup. - Why recursion terminates. A step always goes to a strictly larger value, so you can never come back to a cell on the current chain. That is why there is no "visited" set.
- Try every start. The best path may begin anywhere, so the answer is the maximum of
climbover all cells. The helperall_cellslists them andnbrsyields the in-grid neighbours.
This is the key idea: memoised depth-first search, where the strict increase makes the recursion safe and each cell is solved exactly once.
The key idea
DFS with memoisation; the strict increase rule means there are no cycles. O(rows × cols).
Python solution
def longest_increasing_path(h):
memo = {}
def climb(r, c): # best hike from here
if (r, c) not in memo:
up = [0]
for nr, nc in nbrs(h, r, c):
if h[nr][nc] > h[r][c]:
up.append(climb(nr, nc))
memo[(r, c)] = 1 + max(up)
return memo[(r, c)]
return max(climb(r, c)
for r, c in all_cells(h))
def all_cells(g):
return [(r, c) for r in range(len(g))
for c in range(len(g[0]))]
def nbrs(g, r, c): # in-grid neighbours
R, C = len(g), len(g[0])
for nr, nc in ((r+1, c), (r-1, c),
(r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, ncIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | Exponential: a path is followed again for every route into it | O(R · C) recursion depth in the worst case |
| Memoised DFS (shown code) | O(R · C): each cell is solved once, with four neighbour checks | O(R · C): the memo plus the recursion depth |
Edge cases
- One cell (
[[1]]): returns 1. - All values equal (
[[5, 5], [5, 5]]): returns 1, since the rule is strict. - A single row or column (
[[1, 2, 3, 4]]or[[4], [3], [2], [1]]): returns 4. - Recursion depth: the shown code recurses once per cell on the chain. With Python's default limit of 1000, a single row
[0, 1, ..., 999]already raisesRecursionError, while 990 values still work. A 200 × 200 snake-shaped grid has a path of 40,000 cells and needs a higher limit (sys.setrecursionlimit) or an iterative version. - Empty grid:
all_cellsreadslen(g[0]), so[]would fail, but the problem promises at least one cell. - Plateaus and ties do not cause loops: equal neighbours are simply not climbed.
Common mistakes
- Using
>=instead of>. Equal neighbours then call each other forever (see the quiz). - Only trying right and down neighbours, which misses paths going up or left (
[[9,9,4],[6,6,8],[2,1,1]]would give 2, not 4). - Taking only
climb(0, 0), which ignores paths that start elsewhere (it gives 1 for the same grid). - Forgetting the memo. The answer stays correct but the running time explodes.
Compute the same answer without recursion, so that a 200 × 200 grid with a path of 40,000 cells works with Python's default limit. Describe your approach, then write it if you like.
Compare with our answer
Process cells from the largest value to the smallest. When a cell is handled, every higher neighbour has already been finished, so its answer can be read directly.
def lip_iterative(h):
R, C = len(h), len(h[0])
cells = sorted(((h[r][c], r, c) for r in range(R) for c in range(C)),
reverse=True)
best = [[1] * C for _ in range(R)]
answer = 1
for v, r, c in cells:
for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C and h[nr][nc] > v:
best[r][c] = max(best[r][c], 1 + best[nr][nc])
answer = max(answer, best[r][c])
return answer
It returns 4 for the example grid and 40,000 for a 200 × 200 snake. Time O(R · C · log(R · C)) for the sort, space O(R · C).
A strong answer mentions: sorting by value as a topological order, reading finished neighbours only, and the extra log factor from the sort.
1. You need the longest path in a grid where every step must go to a strictly smaller number (any of four directions). Which approach fits best?
The rule makes the graph acyclic, and the best path from a cell depends only on its lower neighbours, so memoised DFS solves each cell once. A BFS from one corner finds only paths starting there.
2. Why is the shown code O(R · C) even though each call can try four neighbours?
The memo makes climb do real work once per cell, costing four neighbour checks each. It tries all higher neighbours, not only the highest, and it never stops early.
3. A learner changes the test to h[nr][nc] >= h[r][c]. What happens for longest_increasing_path([[5, 5]])?
The cell is stored in memo only after its neighbours return, and with >= the two equal cells call each other endlessly. Running the variant raises RecursionError. With > the same grid returns 1.
Score 60% or more and the lesson is marked complete.