progress

~/problems / 2-D dynamic programming / Grid DP

Longest Increasing Path in a Matrix

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~40 min

A hiking map gives the height of every square of a region as a grid of integers. A trail steps from a square to one of its four neighbours (up, down, left, right; never diagonally, never off the map), and every step must go strictly uphill. A trail may start anywhere.

Implement longest_climb(heights: list[list[int]]) -> int: the number of squares on the longest trail.

longest_climb([
    [9, 9, 4],
    [6, 6, 8],
    [2, 1, 1],
])
# 4   (1 -> 2 -> 6 -> 9)
A 3 by 3 height map with the longest uphill trail drawn as arrows from the 1 in the bottom row to the 2 beside it, up to the 6 and then the 9 in the top-left corner.
longest_climb([
    [3, 4, 5],
    [3, 2, 6],
    [2, 2, 1],
])
# 4   (3 -> 4 -> 5 -> 6)

longest_climb([[7, 7], [7, 7]])   # 1   (flat ground: a trail of one square)
  • 1 <= rows, cols <= 300; heights are in [0, 10^9].
  • ⭐ Bonus: speed tests (one trail winds through the whole map, too deep for recursion in Python) earn a star in O(rows·cols·log(rows·cols)) or better. Following every trail from every square is exponential.
Show hint

The longest trail starting at a square depends only on the longest trails starting at its higher neighbours. If you handle squares from the highest down, those answers are always ready when you need them.

Topic: Grid DP. dp[r][c] from neighbours; add a dimension for extra state (jumps left).

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc