You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j). It starts raining, and water gradually rises over time. At time t, the water level is t, meaning any cell with elevation less than

swimInWater.js

/**
 * @param {number[][]} grid - A 2D grid representing elevations at each cell.
 * @return {number} - Minimum time required to reach bottom-right corner from top-left.
 */
var swimInWater = function (grid) {
  const n = grid.length; // Grid is n x n
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]]; // Possible movement directions: down, up, right, left

  // Custom MinHeap class to prioritize cells with the lowest time (elevation) first
  class MinHeap {
    constructor() { this.a = []; } // Internal array to store heap elements
    size() { return this.a.length; } // Current size of the heap
    peek() { return this.a[0]; } // Peek at the top element (minimum time)
    
    // Insert a new element and maintain heap property
    push(x) {
      this.a.push(x);
      this._siftUp(this.a.length - 1);
    }

    // Remove and return the top element, then reheapify
    pop() {
      const a = this.a;
      const top = a[0];
      const last = a.pop(); // Remove last element
      if (a.length) {
        a[0] = last; // Replace root with last element
        this._siftDown(0); // Restore heap property
      }
      return top;
    }

    // Move element up to maintain heap property
    _siftUp(i) {
      const a = this.a;
      while (i > 0) {
        const p = (i - 1) >> 1; // Parent index
        if (a[p][0] <= a[i][0]) break; // If parent is smaller, stop
        [a[p], a[i]] = [a[i], a[p]]; // Swap with parent
        i = p;
      }
    }

    // Move element down to maintain heap property
    _siftDown(i) {
      const a = this.a;
      const n = a.length;
      while (true) {
        let l = i * 2 + 1, r = l + 1, m = i;
        if (l < n && a[l][0] < a[m][0]) m = l; // Left child smaller
        if (r < n && a[r][0] < a[m][0]) m = r; // Right child smaller
        if (m === i) break; // No swap needed
        [a[m], a[i]] = [a[i], a[m]]; // Swap with smallest child
        i = m;
      }
    }
  }

  // Track visited cells to avoid revisiting
  const seen = Array.from({ length: n }, () => Array(n).fill(false));
  const pq = new MinHeap(); // Priority queue to process cells by minimum time

  // Start from top-left cell with its elevation as initial time
  pq.push([grid[0][0], 0, 0]);

  // Dijkstra-like traversal using min-heap
  while (pq.size()) {
    const [t, r, c] = pq.pop(); // Current time, row, column
    if (seen[r][c]) continue; // Skip if already visited
    seen[r][c] = true; // Mark cell as visited

    // If we've reached bottom-right, return the time
    if (r === n - 1 && c === n - 1) return t;

    // Explore all 4 directions
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc; // Neighbor coordinates
      // Skip out-of-bounds or visited neighbors
      if (nr < 0 || nc < 0 || nr >= n || nc >= n || seen[nr][nc]) continue;
      // Time to reach neighbor is max of current time and neighbor's elevation
      const nt = Math.max(t, grid[nr][nc]);
      pq.push([nt, nr, nc]); // Add neighbor to heap
    }
  }

  // Should never reach here since problem guarantees a path
  return -1;
};