Swim in Rising Water

HardGraphsdijkstra / binary search

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an n x n integer grid grid. Each cell grid[r][c] holds a distinct elevation value. It begins to rain. At time t, the water level across the entire grid is exactly t. You can swim from one cell to any of its four direct neighbors (up, down, left, or right) **only if** the water level is at least as high as the elevations of both the cell you are leaving and the cell you are entering. In other words, at a given time t you may stand on or move through any cell whose elevation is <= t. Moving between two adjacent reachable cells is instantaneous and you may swim any distance within a single instant. Starting at the top-left cell (0, 0), return the **least time** t at which it is possible to reach the bottom-right cell (n - 1, n - 1). The answer is the smallest t such that there exists a path from the start to the destination where every cell on the path has elevation <= t. Equivalently, you want to find the path that minimizes the maximum elevation encountered, and that maximum is the answer.

Examples

Input: grid = [[0,2],[1,3]]
Output: 3
At time 0 you are at cell (0,0). You must eventually reach (1,1) which has elevation 3, so no path can finish before time 3. At t = 3 every cell is submerged and the destination is reachable, so the answer is 3.
Input: 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]]
Output: 16
The best route snakes along the low-elevation cells 0,1,2,3,4,5,...,16. The highest elevation that the optimal path is forced to cross is 16, so the earliest time the destination can be reached is 16.
Input: grid = [[0]]
Output: 0
The single cell is both the start and the destination, so you arrive immediately at time 0.

Constraints

  • `n == grid.length == grid[i].length`
  • `1 <= n <= 50`
  • `0 <= grid[i][j] < n * n`
  • Every value in `grid` is unique (each elevation appears exactly once).

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.