Swim in Rising Water Hard 0 attempts
LeetCode ↗

Swim in Rising Water

Hard HeapPriority Queue LeetCode

You're given an n×n grid where each cell holds an elevation value. Starting at (0,0), you want to reach (n-1,n-1), but at any moment you can only step onto cells whose elevation is at most the current water level t. Find the smallest value of t for which a path from start to finish exists.

Input Format
Implement swimInWater(grid). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
grid = [[0]]
Output
0
Constraints
  • 1 <= n <= 50
  • 0 <= grid[i][j] < n^2
  • Each value in grid is unique
Test Cases (2)
Case 1
Args: [[[0,2],[1,3]]] Expected: 3
Case 2
Args: [[[0]]] Expected: 0
Topics
HeapPriority Queue

Binary Search with BFS Reachability

javascript
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; }
    let head = 0;
  while (head < q.length) {
      const [r,c] = q[head++];
      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.

JavaScript