← DSA Atlas
Dedicated problem page · #778

Swim in Rising Water

HardShortest Path, Dijkstra and Minimum Spanning TreeMinimize the maximum along a path (minimax path)Dijkstra-style min-heap on the path's peak elevation
Solve on LeetCode ↗
778
HardShortest Path, Dijkstra and Minimum Spanning TreeDijkstra-style min-heap on the path's peak elevationMinimize the maximum along a path (minimax path)

Swim in Rising Water

You are given an n x n grid where grid[i][j] is the elevation at cell (i, j). Rain falls and at time t the water level is t everywhere. You can swim from a cell to a 4-directionally adjacent cell only if both cells' elevations are at most the current time t; swimming is instantaneous. Starting at (0, 0), return the least time t at which you can reach (n-1, n-1).

Open official problem prompt ↗
In plain English

Find the earliest moment the rising water lets you walk from the top-left to the bottom-right, which equals the lowest possible peak elevation on any connecting path.

Picture it like this

Like flooding a valley slowly: you can only cross a ridge once the water rises above it, so you wait for exactly the lowest ridge that still connects start to finish.

Example
Input
grid = [[0,2],[1,3]]
Output
3
Why
You must reach the bottom-right cell whose elevation is 3, so no path can complete before time 3.
Constraints
n == grid.length == grid[i].length1 <= n <= 500 <= grid[i][j] < n*nEach value in grid is unique
Pattern lesson

See the pattern, then code

Minimize the maximum along a path (minimax path)
Recognition clue

Reaching a target while minimizing the maximum cell value crossed is a minimax-path problem, solved with a Dijkstra-like heap keyed on the running peak.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. Time equals the highest elevation on your chosen path, so you want the path whose maximum cell is smallest. Always expand the reachable cell with the lowest elevation, tracking the running maximum.

New words, made simpleKnow these before the algorithm
Minimax path
A path chosen to minimize the maximum edge/node value along it.
Running maximum
The highest elevation encountered so far on the current best route.
Frontier
Cells reachable but not yet finalized, held in the heap.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Binary search on time + BFS/DFS

Works and is a clean alternative, but does redundant full searches per guess.

Guess a time t and check if a path uses only cells <= t.

Time O(n^2 log(n^2))Space O(n^2)
Best choiceDijkstra on peak elevation

Single pass; the first time the target is popped gives the optimal minimax time.

Always expand the lowest-elevation reachable cell, tracking the running max until the target is popped.

Time O(n^2 log n)Space O(n^2)
The rule we keep true

Invariant

res holds the minimum possible maximum elevation over all paths from the start to any cell already popped from the heap.

Why this is correct

Reasoning

By always expanding the smallest-elevation frontier cell, the first path reaching the target uses the lowest achievable peak; any alternative reaching it later must cross an equal or higher cell already waiting in the heap.

The algorithm in three movesSay these aloud before coding
1Push the start cell keyed by its elevation into a min-heap

pq=[(0,0,0)] res=0

2Pop the smallest-elevation frontier cell and update the running max time

pop 0 -> push (2,0,1),(1,1,0)

3If it is the bottom-right cell, return that running max

pop 1 -> push (3,1,1); pop 2; pop 3 -> res=3

4Push unvisited neighbors keyed by their own elevation

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
21
12
33
1 · Readcell (0,0)=0
2 · AskPeak so far?
3 · Update statepq=[(0,0,0)], res=0
4 · ResultPop it, res=max(0,0)=0
Key takeaway

Path from top-left to bottom-right; answer is the highest elevation crossed.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Seed the heap

    Start from (0,0) keyed by its elevation; res tracks the running peak.

  2. 2
    Lines 8-10Pop and update peak

    The popped cell's elevation can only raise res, the current best max.

  3. 3
    Lines 11-12Target check

    When the bottom-right cell is popped, res is the optimal answer.

  4. 4
    Lines 13-18Push neighbors

    Enqueue unseen neighbors keyed by their elevation; mark seen on push to avoid duplicates.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • n == 1 -> answer is grid[0][0]
  • Answer is always at least max(grid[0][0], grid[n-1][n-1])
  • Monotone increasing snake path forcing the max value
  • Large plateau of low cells with one high barrier
!

Common beginner mistakes

  • Adding elevations along the path instead of taking their maximum (this is minimax, not min-sum)
  • Marking cells seen on pop rather than on push, allowing duplicate heap entries
  • Forgetting the answer cannot be below the start or target elevation
Check your understanding

Why does the running maximum, not the sum of elevations, determine the time?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)#1135Connecting Cities With Minimum CostMinimum spanning tree (Kruskal)