The problem
A grid of ground heights floods: at time t, the water level is t. You can swim between neighbouring squares if both are ≤ t. Find the earliest time you can swim from the top-left to the bottom-right.
Input: the 5 × 5 heights shown Output: 16
Picture it
Picture a valley slowly flooding. Your route is only as good as its highest square, since you must wait until the water covers it. We always explore next the reachable square needing the lowest water (a min-heap). The highest square we were forced to step on by the time we reach the corner is the answer.
How to recognise it
- A grid where each cell has a height or threshold, and you move between neighbours.
- The cost of a route is the largest value on it, not the sum of its values.
- You want the route whose worst moment is as small as possible, with free choice of direction at every step.
- With n up to 50 the grid has 2,500 cells, so repeating a full search per possible time is fine, but you can do much better.
Start with brute force
Try each water level t = 0, 1, 2, … in turn. For each t, run a BFS from the top-left that may enter only cells with height at most t, and stop at the first t for which the bottom-right is reached.
def swim_brute(grid):
n = len(grid)
for t in range(n * n):
if grid[0][0] > t:
continue
seen, q = {(0, 0)}, deque([(0, 0)])
while q:
r, c = q.popleft()
if (r, c) == (n - 1, n - 1):
return t
for nr, nc in nbrs(grid, r, c):
if (nr, nc) not in seen and grid[nr][nc] <= t:
seen.add((nr, nc))
q.append((nr, nc))
The grid holds the heights 0 to n² − 1, so there are up to n² levels, and each BFS costs O(n²): O(n⁴) in total. For n = 50 that is about 6 × 10^6 steps, which is acceptable, but for n = 500 it is about 6 × 10^10. Space is O(n²).
From brute force to the idea
- Find the waste. Each BFS restarts from the top-left and rediscovers the cells it reached for a lower t.
- Raise the level only as needed. Instead of trying every t, keep the cheapest frontier: the cell that can be entered at the lowest water level.
- Cost of reaching a cell. If you stand at a cell where the level had to be
t, entering a neighbour needsmax(t, height of the neighbour). A route's cost is the highest cell on it. - Use a min-heap, as in Dijkstra.
heapholds(level needed, row, column). Popping gives the cell reachable at the lowest level. The first time the bottom-right is popped, its level is the answer. - Mark when pushing. A cell is added to
seenwhen first pushed. The first cell to discover it is the one popped earliest, with the lowestt, so the cost it assigns is already the smallest possible.
The key idea: this is Dijkstra with "max" in place of "plus", because water must rise to the highest cell on the route.
The key idea
Dijkstra-style search where a path’s cost is its maximum height, not its sum.
Python solution
def swim_in_water(grid):
n = len(grid)
heap = [(grid[0][0], 0, 0)]
seen = {(0, 0)}
while heap:
t, r, c = heappop(heap) # lowest
if (r, c) == (n - 1, n - 1):
return t
for nr, nc in nbrs(grid, r, c):
if (nr, nc) not in seen:
seen.add((nr, nc))
tt = max(t, grid[nr][nc])
heappush(heap, (tt, nr, nc))
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, ncLeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop
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
| Approach | Time | Space |
|---|---|---|
| Try every water level (brute force) | O(n⁴): up to n² levels, each with a BFS over n² cells | O(n²): the seen set and queue |
| Heap search (shown code) | O(n² log n): each of the n² cells is pushed once, and each heap operation costs O(log n²) = O(log n) | O(n²): the heap and the seen set |
Edge cases
- One cell (
[[0]]): returnsgrid[0][0], here 0. A start cell of height 5 also gives 5, since you must wait for it. - High corners: the answer is at least the larger of the two corner heights, because both lie on every route.
- A winding route: the 5 × 5 snake grid
[[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]returns 16. - Four directions only: diagonal moves are not allowed.
- Imports:
heappushandheappop, and the helpernbrs.
Common mistakes
- Adding the heights along the route, which is the wrong measure for "highest cell on the route".
- Using only the neighbour's height,
grid[nr][nc], and forgetting the running maximumt. - Running a plain BFS (it counts steps, not water level).
- Restricting moves to right and down, which misses routes that wind around high cells.
Each cell is a height. The effort of a step is the absolute height difference between two neighbouring cells, and a route's effort is its largest step. Return the smallest possible effort from the top-left to the bottom-right (any rectangular grid). Describe what changes, then write it if you like.
Compare with our answer
It is the same "minimise the maximum" search, but a step's cost now depends on the pair of cells, not just the cell entered. That breaks marking at push time, because a later cell might reach a neighbour with a smaller step. Keep the best known effort per cell and skip stale entries.
def min_effort(h):
R, C = len(h), len(h[0])
best = {(0, 0): 0}
heap = [(0, 0, 0)]
while heap:
t, r, c = heappop(heap)
if (r, c) == (R - 1, C - 1):
return t
if t > best[(r, c)]:
continue
for nr, nc in nbrs(h, r, c):
tt = max(t, abs(h[nr][nc] - h[r][c]))
if tt < best.get((nr, nc), inf):
best[(nr, nc)] = tt
heappush(heap, (tt, nr, nc))
min_effort([[1,2,2],[3,8,2],[5,3,5]]) is 2. Time O(R·C·log(R·C)), space O(R·C).
A strong answer mentions: max instead of sum as the combining rule, the cost now depending on each step, and why a per-cell best value replaces the seen set.
1. A network of toll roads joins your home to your destination. A trip's cost is the single largest toll you pay on it, and you can choose any route. Which approach fits best?
The cost of a route is the maximum toll, so the search must combine costs with max instead of plus. Adding tolls measures a different quantity, and BFS or a one-way DP ignores the cost rule or the freedom of direction.
2. Why does the shown code run in O(n² log n) time?
The n² cells enter seen as they are pushed, so there are at most n² pushes and pops, each costing O(log n²) = O(log n). Pushes happen once per cell, not once per neighbour, and the heap changes throughout the search.
3. A learner changes tt = max(t, grid[nr][nc]) to tt = grid[nr][nc]. Which input now returns a wrong answer?
Without the running maximum, the route 0, 2, 1 is priced by its last cell alone, so the answer comes out as 1 although the water must reach 2. In the other inputs the last cell is also the highest on the best route.
Score 60% or more and the lesson is marked complete.