Swim in Rising Water — DSA · Engineering Playbook

Problem#

An n x n grid where grid[i][j] is the platform’s elevation. At time t, you can move into any cell whose elevation is at most t. Return the minimum time to travel from (0, 0) to (n-1, n-1).

Examples#

grid = [[0,2],[1,3]] → 3
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]] → 16

Constraints#

n == grid.length == grid[i].length, 1 <= n <= 50, 0 <= grid[i][j] < n^2.

Approach#

Treat the grid as a graph where the “cost” of a path is the maximum elevation along it. Use Dijkstra with a min-heap ordered by max-elevation-so-far; pop the smallest, expand to neighbors with max(curCost, neighborHeight).

Solution#

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
        priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
        dist[0][0] = grid[0][0];
        pq.push({grid[0][0], 0, 0});
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        while (!pq.empty()) {
            auto [d, r, c] = pq.top(); pq.pop();
            if (r == n - 1 && c == n - 1) return d;
            if (d > dist[r][c]) continue;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dx[k], nc = c + dy[k];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                int nd = max(d, grid[nr][nc]);
                if (nd < dist[nr][nc]) {
                    dist[nr][nc] = nd;
                    pq.push({nd, nr, nc});
                }
            }
        }
        return -1;
    }
};

import (
  "container/heap"
  "math"
)

type swimItem struct{ d, r, c int }
type swimPQ []swimItem

func (h swimPQ) Len() int            { return len(h) }
func (h swimPQ) Less(i, j int) bool  { return h[i].d < h[j].d }
func (h swimPQ) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *swimPQ) Push(x interface{}) { *h = append(*h, x.(swimItem)) }
func (h *swimPQ) Pop() interface{}   { o := *h; n := len(o); x := o[n-1]; *h = o[:n-1]; return x }

func swimInWater(grid [][]int) int {
  n := len(grid)
  dist := make([][]int, n)
  for i := range dist {
    dist[i] = make([]int, n)
    for j := range dist[i] {
      dist[i][j] = math.MaxInt32
    }
  }
  dist[0][0] = grid[0][0]
  pq := &swimPQ{{grid[0][0], 0, 0}}
  dx := []int{1, -1, 0, 0}
  dy := []int{0, 0, 1, -1}
  for pq.Len() > 0 {
    cur := heap.Pop(pq).(swimItem)
    d, r, c := cur.d, cur.r, cur.c
    if r == n-1 && c == n-1 {
      return d
    }
    if d > dist[r][c] {
      continue
    }
    for k := 0; k < 4; k++ {
      nr, nc := r+dx[k], c+dy[k]
      if nr < 0 || nr >= n || nc < 0 || nc >= n {
        continue
      }
      nd := d
      if grid[nr][nc] > nd {
        nd = grid[nr][nc]
      }
      if nd < dist[nr][nc] {
        dist[nr][nc] = nd
        heap.Push(pq, swimItem{nd, nr, nc})
      }
    }
  }
  return -1
}

import heapq
from typing import List

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dist = [[float('inf')] * n for _ in range(n)]
        dist[0][0] = grid[0][0]
        pq = [(grid[0][0], 0, 0)]
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while pq:
            d, r, c = heapq.heappop(pq)
            if r == n - 1 and c == n - 1:
                return d
            if d > dist[r][c]:
                continue
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if nr < 0 or nr >= n or nc < 0 or nc >= n:
                    continue
                nd = max(d, grid[nr][nc])
                if nd < dist[nr][nc]:
                    dist[nr][nc] = nd
                    heapq.heappush(pq, (nd, nr, nc))
        return -1

class MinHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(x) {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                let l = i * 2 + 1, r = i * 2 + 2, s = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

var swimInWater = function(grid) {
    const n = grid.length;
    const dist = Array.from({ length: n }, () => new Array(n).fill(Infinity));
    dist[0][0] = grid[0][0];
    const pq = new MinHeap();
    pq.push([grid[0][0], 0, 0]);
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    while (pq.size()) {
        const [d, r, c] = pq.pop();
        if (r === n - 1 && c === n - 1) return d;
        if (d > dist[r][c]) continue;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            const nd = Math.max(d, grid[nr][nc]);
            if (nd < dist[nr][nc]) {
                dist[nr][nc] = nd;
                pq.push([nd, nr, nc]);
            }
        }
    }
    return -1;
};

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] dist = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = grid[0][0];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{grid[0][0], 0, 0});
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], r = cur[1], c = cur[2];
            if (r == n - 1 && c == n - 1) return d;
            if (d > dist[r][c]) continue;
            for (int k = 0; k < 4; k++) {
                int nr = r + dx[k], nc = c + dy[k];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                int nd = Math.max(d, grid[nr][nc]);
                if (nd < dist[nr][nc]) {
                    dist[nr][nc] = nd;
                    pq.offer(new int[]{nd, nr, nc});
                }
            }
        }
        return -1;
    }
}

class MinHeap {
    h: number[][] = [];
    size(): number { return this.h.length; }
    push(x: number[]): void {
        this.h.push(x);
        let i: number = this.h.length - 1;
        while (i > 0) {
            const p: number = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): number[] {
        const top: number[] = this.h[0];
        const last: number[] = this.h.pop() as number[];
        if (this.h.length) {
            this.h[0] = last;
            let i: number = 0;
            const n: number = this.h.length;
            while (true) {
                let l: number = i * 2 + 1, r: number = i * 2 + 2, s: number = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function swimInWater(grid: number[][]): number {
    const n: number = grid.length;
    const dist: number[][] = Array.from({ length: n }, () => new Array(n).fill(Infinity));
    dist[0][0] = grid[0][0];
    const pq: MinHeap = new MinHeap();
    pq.push([grid[0][0], 0, 0]);
    const dirs: number[][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    while (pq.size()) {
        const [d, r, c] = pq.pop();
        if (r === n - 1 && c === n - 1) return d;
        if (d > dist[r][c]) continue;
        for (const [dr, dc] of dirs) {
            const nr: number = r + dr, nc: number = c + dc;
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            const nd: number = Math.max(d, grid[nr][nc]);
            if (nd < dist[nr][nc]) {
                dist[nr][nc] = nd;
                pq.push([nd, nr, nc]);
            }
        }
    }
    return -1;
}

Editorial#

The “max along path” cost is a valid Dijkstra metric because it’s monotonic when extended. Each cell’s optimal entry-time is the smallest max-height of any path reaching it. The heap is sized by n^2 and each cell relaxes at most O(1) times.

Complexity#

Time: O(n^2 log n).
Space: O(n^2).

Concept revision#

Network Delay Time