Swim In Rising Water

The problem

grid is a square of cells, each with a height. Every height from 0 up to the number of cells minus 1 appears exactly once. Rain raises the water: at time t the water level is t everywhere. You start in the top-left cell and want to reach the bottom-right cell. You may be in a cell only when its height is at most the water level, and you move between cells that share a side. Swimming itself takes no time. Return the earliest time at which you can reach the bottom-right cell. For a grid of one cell that is time 0.

What to write

function solve(grid: number[][]): number

Input
grid = [[0,2],[1,3]]

Output
3

Input
grid = [[0]]

Output
0

Constraints

The n × n grid contains distinct elevations from 0 to n²-1.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Every height from 0 to the highest cell appears once, so the answer is one of those numbers. It can never be lower than the height of the start cell or of the end cell, because you have to be in both. And at the highest height in the grid, every cell is under water.

2. Hint 2: Ask a smaller question

   Forget "earliest" for a moment. Freeze the water at one level, say 2 in example 1. Which cells are under water, and can you get from the top-left cell to the bottom-right one through them? How would you check that for any level?

3. Hint 3: Name the pattern

   If the end can be reached at some level, it can be reached at every higher level too. So the levels are a run of "no" followed by a run of "yes", and you want the first "yes". That is binary search on the answer. Each test is a flood fill: spread from the start through the cells under water. Read the lesson on binary search on the answer.

4. Hint 4: State the invariant

   Keep a range of levels that always contains the answer. A level that passes the test might be the earliest, so it stays in the range. A level that fails cannot be the answer, and neither can any lower level, so they all leave.

5. Hint 5: Sketch the pseudocode

   low = the higher of the start and end heights, high = the largest height. While low < high: mid = the middle, rounded down. Flood fill from the start through cells with height at most mid. If the fill reaches the end: high = mid. Otherwise: low = mid + 1. Return low.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Binary-search the water level and use flood fill to test reachability at each candidate level.

The slow way

Try time 0, then 1, then 2, and so on. At each time, start at the top-left cell and spread through the cells that are under water to see whether the bottom-right cell is reached. Return the first time that works. It is correct, but a grid of n × n cells has n × n times to try, and each try can visit every cell.

The insight

Water only rises, so a cell that is under water stays under water. If you can reach the end at one level, you can reach it at every higher level. So the levels form a run of "no" followed by a run of "yes": in example 1 the answers for levels 0 to 3 are no, no, no, yes. One test in the middle tells you which half to drop.

Step by step

1. Test one water level with a flood fill from the top-left cell. A flood fill starts at one cell and keeps spreading to neighboring cells that qualify, here the cells under water. A start cell above the water fails at once; the search never asks for such a level.
2. The fill reached the bottom-right cell: this level is enough. The fill only ever moves between cells that are under water at this level, so reaching the end cell proves that a swim from start to end exists.
3. Add each neighbor that is under water and not seen to the fill. You can swim to a cell next to you only if its height is at most the level. Marking a cell as seen when it is added keeps the fill from walking in circles.
4. The fill ran out without reaching the end: this level is too low. Every cell you can swim to at this level has been visited, and the end cell was not among them. So the water has to rise further.
5. Search from the higher of the start and end cells to the highest cell. You must be in both the start and the end cell, so the water has to cover the higher of the two. At the highest height in the grid everything is under water, so that level always works.
6. Test the middle level and keep the half that can hold the answer. If the middle level works, the answer is that level or lower. If it fails, every lower level fails too, so the answer is higher. Halving the range like this is called binary search.
7. One level is left: that is the answer. The range always held the answer and lost at least one level per round. The single level that remains is the earliest time the end can be reached.

The same numbered steps are the comments in each solution.

function solve(grid) {
  // The grid is n cells wide and n cells high.
  const n = grid.length;
  // 1. Test one water level with a flood fill from the top-left cell
  function possible(t) {
    // Nothing can start from a cell that is still above the water.
    if (grid[0][0] > t) return false;
    // A Set compares arrays by identity, not by content, so a cell is
    // remembered as one number: its row times n plus its column.
    const q = [[0, 0]],
      seen = new Set([0]);
    // Removing the first item of an array is slow, so nothing is removed:
    // i is the position of the front of the queue, and push adds at the back.
    for (let i = 0; i < q.length; i++) {
      const [r, c] = q[i];
      // 2. The fill reached the bottom-right cell: this level is enough
      if (r === n - 1 && c === n - 1) return true;
      // 3. Add each neighbor that is under water and not seen to the fill
      for (const [a, b] of [
        [r + 1, c],
        [r - 1, c],
        [r, c + 1],
        [r, c - 1],
      ])
        if (
          a >= 0 &&
          a < n &&
          b >= 0 &&
          b < n &&
          !seen.has(a * n + b) &&
          grid[a][b] <= t
        ) {
          seen.add(a * n + b);
          q.push([a, b]);
        }
    }
    // 4. The fill ran out without reaching the end: this level is too low
    return false;
  }
  // 5. Search from the higher of the start and end cells to the highest cell
  let l = Math.max(grid[0][0], grid[n - 1][n - 1]),
    r = n * n - 1;
  while (l < r) {
    // 6. Test the middle level and keep the half that can hold the answer
    // The shift >>> 1 halves the sum and rounds down.
    const m = (l + r) >>> 1;
    if (possible(m)) r = m;
    else l = m + 1;
  }
  // 7. One level is left: that is the answer
  return l;
}

function solve(grid: number[][]): number {
  // The grid is n cells wide and n cells high.
  const n = grid.length;
  // 1. Test one water level with a flood fill from the top-left cell
  function possible(t: number): boolean {
    // Nothing can start from a cell that is still above the water.
    if (grid[0][0] > t) return false;
    // A Set compares arrays by identity, not by content, so a cell is
    // remembered as one number: its row times n plus its column.
    const q = [[0, 0]],
      seen = new Set([0]);
    // Removing the first item of an array is slow, so nothing is removed:
    // i is the position of the front of the queue, and push adds at the back.
    for (let i = 0; i < q.length; i++) {
      const [r, c] = q[i];
      // 2. The fill reached the bottom-right cell: this level is enough
      if (r === n - 1 && c === n - 1) return true;
      // 3. Add each neighbor that is under water and not seen to the fill
      for (const [a, b] of [
        [r + 1, c],
        [r - 1, c],
        [r, c + 1],
        [r, c - 1],
      ])
        if (
          a >= 0 &&
          a < n &&
          b >= 0 &&
          b < n &&
          !seen.has(a * n + b) &&
          grid[a][b] <= t
        ) {
          seen.add(a * n + b);
          q.push([a, b]);
        }
    }
    // 4. The fill ran out without reaching the end: this level is too low
    return false;
  }
  // 5. Search from the higher of the start and end cells to the highest cell
  let l = Math.max(grid[0][0], grid[n - 1][n - 1]),
    r = n * n - 1;
  while (l < r) {
    // 6. Test the middle level and keep the half that can hold the answer
    // The shift >>> 1 halves the sum and rounds down.
    const m = (l + r) >>> 1;
    if (possible(m)) r = m;
    else l = m + 1;
  }
  // 7. One level is left: that is the answer
  return l;
}

from collections import deque


def solve(grid):
    # The grid is n cells wide and n cells high.
    n = len(grid)

    # 1. Test one water level with a flood fill from the top-left cell
    def reachable(level):
        # Nothing can start from a cell that is still above the water.
        if grid[0][0] > level:
            return False
        # A deque is a list that is fast at both ends: append adds at the back,
        # popleft takes from the front.
        queue = deque([(0, 0)])
        seen = {(0, 0)}
        while queue:
            r, c = queue.popleft()
            # 2. The fill reached the bottom-right cell: this level is enough
            if r == n - 1 and c == n - 1:
                return True
            # 3. Add each neighbor that is under water and not seen to the fill
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if (
                    0 <= nr < n
                    and 0 <= nc < n
                    and (nr, nc) not in seen
                    and grid[nr][nc] <= level
                ):
                    seen.add((nr, nc))
                    queue.append((nr, nc))
        # 4. The fill ran out without reaching the end: this level is too low
        return False

    # 5. Search from the higher of the start and end cells to the highest cell
    low = max(grid[0][0], grid[n - 1][n - 1])
    high = n * n - 1
    while low < high:
        # 6. Test the middle level and keep the half that can hold the answer
        mid = (low + high) // 2
        if reachable(mid):
            high = mid
        else:
            low = mid + 1
    # 7. One level is left: that is the answer
    return low

Example 1, traced

Input
grid = [[0,2],[1,3]]

Output
3

Why it works

The range always contains the answer. A level that passes the test stays, because it might be the earliest. A level that fails leaves together with every lower level, because less water never opens a new way. Each round removes at least one level, so the loop ends with the earliest level that works.

Time and space

Time O(n² log n), extra space O(n²). An n × n grid has n × n levels; halving them takes about 2 log n rounds. Each round is one flood fill that visits every cell at most once: O(n² log n) time. The waiting cells and seen marks hold up to n × n cells: O(n²) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• The higher of start and end is only a lower limit, though both examples return it. In [[0,3],[2,1]] those cells are 0 and 1, but every way to the end passes a 2 or a 3: the answer is 2.
• A level that passes might be the answer, so keep it in the range. With the upper end moved to one below it, [[0,3],[2,1]] goes wrong: level 2 passes, only level 1 is left, and 1 is returned, not 2.
• A cell is under water when its height is at most the level, not only when it is below. Testing with "below" makes the small grid [[0,3],[2,1]] return 3 instead of 2.

Pattern

Binary search on the answer. Builds on Koko Eating Bananas and Number of Islands.

Keep going