Swim in Rising Water | Problems

Given an n×n grid where grid[i][j] represents elevation, find the minimum time t such that you can swim from (0,0) to (n-1,n-1) where you can only enter cells with elevation <= t.

Example: grid = [[0,2],[1,3]] → Output: 3

Sample Input

—

Sample Output

—

Constraints

1 <= n <= 50
0 <= grid[i][j] < n^2
Each value in grid is unique

Test Cases

Case 1

Args: [[[0,2],[1,3]]] Expected: 3

Topics

Heap Priority Queue

Binary Search + BFS / Dijkstra

function swimInWater(grid) {
  const n = grid.length, dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  let lo = grid[0][0], hi = n*n-1;
  while (lo < hi) {
    const mid = (lo+hi)>>1;
    const visited = Array.from({length:n}, ()=>Array(n).fill(false));
    const q = [[0,0]]; visited[0][0] = true;
    if (grid[0][0] > mid) { lo = mid+1; continue; }
    while (q.length) {
      const [r,c] = q.shift();
      for (const [dr,dc] of dirs) {
        const nr=r+dr,nc=c+dc;
        if (nr>=0&&nr<n&&nc>=0&&nc<n&&!visited[nr][nc]&&grid[nr][nc]<=mid) { visited[nr][nc]=true; q.push([nr,nc]); }
      }
    }
    if (visited[n-1][n-1]) hi = mid; else lo = mid+1;
  }
  return lo;
}

Time: O(n² log n) | Space: O(n²)

Saved in this browser only. Private to you.