Swim in Rising Water

Examples

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

At time 3, every cell's elevation (0, 2, 1, 3) is at most 3, so all cells (and thus a path between the corners) become usable. No smaller time makes all needed cells usable.

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

There's a path along which the highest elevation you must cross is 16, and no path avoids needing to cross at least elevation 16.

Constraints

• n == grid.length == grid[i].length

• 1 <= n <= 50

• 0 <= grid[i][j] < n^2

• Every value in grid is unique.

Approach

Reframe the question: for any path from the top-left to the bottom-right, define its "cost" as the highest single elevation you must step on along that path. The answer is the minimum such cost over all possible paths - because that's exactly the earliest time at which the water level is high enough for a fully swimmable path to exist.

That reframing turns this into a shortest-path problem where "combining" two path segments takes the max of their costs instead of the sum - so a Dijkstra-style approach works: always expand the reachable cell with the smallest "highest elevation so far," and finalize cells in that order, exactly like normal Dijkstra but comparing/combining with Math.max instead of +.

A different, equally valid strategy is binary search on the answer: guess a time T, and check with a simple BFS/DFS (only stepping on cells with elevation <= T) whether the destination is reachable. Since reachability only ever improves as T grows, binary search for the smallest T that works.

Solutions

Binary Search + BFS

The set of times T for which the destination is reachable (using only cells with elevation <= T) is "monotonic": once reachable at some T, it stays reachable for every larger T too (more cells only ever become usable as T grows, never fewer). That monotonicity is exactly what binary search needs. Binary search over candidate times from 0 to n * n - 1 (the largest possible elevation), and for each candidate T run a BFS/DFS from (0, 0) that may only step on cells with elevation <= T, checking whether (n - 1, n - 1) is reached. Find the smallest T for which it is.

function swimInWater(grid) {
  const n = grid.length;

  function canReachBy(T) {
    if (grid[0][0] > T) return false;
    const visited = Array.from({ length: n }, () => new Array(n).fill(false));
    const stack = [[0, 0]];
    visited[0][0] = true;

    while (stack.length > 0) {
      const [r, c] = stack.pop();
      if (r === n - 1 && c === n - 1) return true;

      for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
        const nr = r + dr;
        const nc = c + dc;
        if (
          nr >= 0 && nr < n && nc >= 0 && nc < n &&
          !visited[nr][nc] && grid[nr][nc] <= T
        ) {
          visited[nr][nc] = true;
          stack.push([nr, nc]);
        }
      }
    }
    return visited[n - 1][n - 1];
  }

  let low = Math.max(grid[0][0], grid[n - 1][n - 1]);
  let high = n * n - 1;
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (canReachBy(mid)) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  return low;
}

Time: O(n^2 log(n^2)) - each of the O(log(n^2)) binary search steps runs an O(n^2) grid traversal · Space: O(n^2) for the visited grid and traversal stack

Optimal - Dijkstra-Style Search

Treat each grid cell as a graph node, connected to its four neighbors. The "distance" to reach a cell along a given path is the highest elevation stepped on anywhere along that path, and combining a step onto a new cell takes Math.max(costSoFar, newCell's elevation) rather than a sum. Run Dijkstra's algorithm with that modified combining rule: use a min-heap keyed on this "highest elevation so far" cost, always expand the cheapest not-yet-finalized cell, and stop as soon as the bottom-right cell is finalized - its cost is the answer.

function swimInWater(grid) {
  const n = grid.length;
  const best = Array.from({ length: n }, () => new Array(n).fill(Infinity));
  best[0][0] = grid[0][0];

  const heap = [[grid[0][0], 0, 0]];
  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent][0] <= heap[i][0]) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  }
  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        let smallest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
        if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
        if (smallest === i) break;
        [heap[smallest], heap[i]] = [heap[i], heap[smallest]];
        i = smallest;
      }
    }
    return top;
  }

  const visited = Array.from({ length: n }, () => new Array(n).fill(false));

  while (heap.length > 0) {
    const [cost, r, c] = pop();
    if (visited[r][c]) continue;
    visited[r][c] = true;
    if (r === n - 1 && c === n - 1) return cost;

    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= n || nc < 0 || nc >= n || visited[nr][nc]) continue;

      const newCost = Math.max(cost, grid[nr][nc]);
      if (newCost < best[nr][nc]) {
        best[nr][nc] = newCost;
        push([newCost, nr, nc]);
      }
    }
  }

  return best[n - 1][n - 1];
}

Time: O(n^2 log n), since each of the n^2 cells can be pushed onto the heap a constant number of times · Space: O(n^2) for the best-cost grid, visited grid, and heap