LeetCode 778 · Hard · Advanced Graphs

Swim in Rising Water

Each cell of an n × n grid has a distinct elevation. At time t the water is t deep everywhere, and you can swim between neighbouring cells whose elevations are both at most t. Return the earliest time you can get from the top-left to the bottom-right cell.

O(n² log n)time
O(n²)space
min-heapkeyed by max height so far

square grid, 2×2 to 5×5 · the values must be 0 to n²−1, each exactly once

Elevation · corner = time to reach that cell · blue = under water, not yet explored

minH · [t, r, c], lowest t first

public int swimInWater(int[][] grid) { int n = grid.length; boolean[][] visit = new boolean[n][n]; PriorityQueue<int[]> minH = new PriorityQueue<>((a, b) -> a[0] - b[0]); minH.offer(new int[]{grid[0][0], 0, 0}); // {max, r, c} int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; visit[0][0] = true; while (!minH.isEmpty()) { int[] cur = minH.poll(); int t = cur[0]; int r = cur[1]; int c = cur[2]; if (r == n - 1 && c == n - 1) { return t; } for (int[] d : directions) { int neiR = r + d[0]; int neiC = c + d[1]; if (neiR < 0 || neiC < 0 || neiR == n || neiC == n || visit[neiR][neiC]) { continue; } visit[neiR][neiC] = true; int h = Math.max(t, grid[neiR][neiC]); minH.offer(new int[]{h, neiR, neiC}); } } return -1;}
[t, r, c]
—
max so far
—
visit
1
heap size
1

Why it works

  1. Brute force tries every time: for t = 0, 1, 2, … run a BFS through cells with elevation ≤ t until the corner is reachable: O(n⁴). Binary search on t cuts it to O(n² log n²).
  2. The cost of a path is its highest cell, not a sum. Dijkstra still works with "max" in place of "+": the heap always expands the cell reachable with the lowest peak so far, and a peak never goes down along a path.
  3. The first time the corner pops, its key is final: every cheaper frontier cell was already expanded. Each of the n² cells is pushed once: O(n² log n) time, O(n²) space.
  4. Pitfall: the start counts. If grid[0][0] is high, you wait for it too, which is why the heap starts with grid[0][0], not 0. Marking cells visited when pushed, not when popped, is safe here because a cell's key can't improve later: the heap pops keys in increasing order.
  5. Related: Path With Minimum Effort (1631) uses the same heap with the biggest step instead of the biggest cell. Network Delay Time (743) is the sum version.