LeetCode 329 · 2-D DP

Longest Increasing Path in a Matrix, explained with a picture

The longest uphill hike on a terrain map.

Hard2-D DP
▶ Watch it step by step

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

  1. 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.
  2. 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 best climb among higher neighbours, or just 1 when none is higher.
  3. Save it. The dictionary memo stores each result, so a cell is solved once and later visits are a lookup.
  4. 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.
  5. Try every start. The best path may begin anywhere, so the answer is the maximum of climb over all cells. The helper all_cells lists them and nbrs yields 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, nc

In 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

ApproachTimeSpace
Brute forceExponential: a path is followed again for every route into itO(R · C) recursion depth in the worst case
Memoised DFS (shown code)O(R · C): each cell is solved once, with four neighbour checksO(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 raises RecursionError, 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_cells reads len(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.
Your turn: no recursion

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.

Check what stuck

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?

2. Why is the shown code O(R · C) even though each call can try four neighbours?

3. A learner changes the test to h[nr][nc] >= h[r][c]. What happens for longest_increasing_path([[5, 5]])?

Score 60% or more and the lesson is marked complete.