Swim in Rising Water
Hard · Advanced Graphs · Array · Binary Search · Depth-First Search · Breadth-First Search · Union Find · Heap (Priority Queue) · Matrix
Problem
You are given an n x n grid where grid[i][j] is the elevation of cell (i, j). Rain makes the water level rise: at time t the water depth everywhere is t.
You can swim from a cell to an up, down, left or right neighbor only if both cells have elevation at most t. Swimming itself takes no time, so you can cover any distance within one moment. You start at (0, 0).
Return the least time t at which you can reach the bottom-right cell (n - 1, n - 1).
Examples
Input: grid = [[0,5],[3,1]] Output: 3
At time 3 you can swim down to the 3 and then across to the 1; the 5 is never needed.
Input: grid = [[0,2,1],[7,8,3],[6,5,4]] Output: 4
The route 0 → 2 → 1 → 3 → 4 has highest elevation 4, so you wait until time 4.
Input: grid = [[8,0,1],[2,3,4],[5,6,7]] Output: 8
The start cell itself has elevation 8, the highest in the grid, so nothing can happen before time 8.
Constraints
- n == len(grid) == len(grid[i])
- 1 <= n <= 50
- 0 <= grid[i][j] < n²
- Every value in grid is unique
Approaches
- Binary search on the time, flood fill to test it — time O(n² log n), space O(n²)
Follow-up
The same greedy order also falls out of union-find: sort the cells by height, add them one at a time, join each to its already-added neighbors, and stop when the two corners are in the same set. See the use cases for the mirror question (the path whose lowest cell is highest) and for crossing from a whole row to another.
Related problems
Start free on Cariara · Coding problems · System design studio
