Swim in Rising Water

NeetCode: Swim in Rising Water · LeetCode: 778. Swim in Rising Water · Difficulty: Hard

You have an n x n grid where grid[r][c] is the elevation of a cell; the values are a permutation of 0..n*n - 1. At time t the water depth is t everywhere, and you may swim between 4-adjacent cells if both have elevation <= t. You start at the top-left at time 0. Return the least time at which you can reach the bottom-right.

Example

Text

Input:  grid = [[0, 2], [1, 3]]                                   Output: 3
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

The cost of a path is the highest cell on it, and the goal is the path that minimises that maximum. This is a bottleneck (minimax) path problem.

Brute force: binary search on the time, then BFS

If you can swim at time t, you can also swim at any later time, so feasibility is monotonic. Binary search the smallest t for which a flood fill from the top-left, restricted to cells with elevation <= t, reaches the bottom-right.

The flood fill uses an ArrayDeque<int[]> as the queue. Java's ArrayDeque does not accept null, which does not matter here because every entry is an int[]{row, column}.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private boolean canReach(int[][] grid, int t) {
        int n = grid.length;
        if (grid[0][0] > t) return false;
        boolean[][] seen = new boolean[n][n];
        Deque<int[]> queue = new ArrayDeque<>();
        seen[0][0] = true;
        queue.add(new int[] {0, 0});
        int[][] dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];
            if (r == n - 1 && c == n - 1) return true;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
                if (!seen[nr][nc] && grid[nr][nc] <= t) {
                    seen[nr][nc] = true;
                    queue.add(new int[] {nr, nc});
                }
            }
        }
        return false;
    }

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int lo = 0, hi = n * n - 1; // at t = n*n - 1 everything is passable
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canReach(grid, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.swimInWater(new int[][] {{0, 2}, {1, 3}}));
        int[][] big = {
            {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}
        };
        System.out.println(s.swimInWater(big));
        System.out.println(s.swimInWater(new int[][] {{0}}));
    }
}

Output

3
16
0

There are log(n^2) BFS runs, each touching n^2 cells. Time: O(n^2 log n). Space: O(n^2).

Optimal: Dijkstra-style min-heap on the maximum elevation

Run Dijkstra, but define the "distance" of a path as the maximum elevation along it instead of a sum. Steps:

Push the start cell into a min-heap keyed by elevation and mark it seen.
Pop the lowest frontier cell and raise the water level t to at least its elevation.
If it is the bottom-right cell, return t.
Otherwise push its unseen neighbours (marking them seen when pushed) and repeat.

The first time the bottom-right cell is popped, t is the answer: any cheaper route would have needed a lower frontier cell, which was already popped. This has the same asymptotic cost as binary search plus BFS (the heap's log replaces the search's log), and it is one pass with no search bounds to get wrong.

Java's PriorityQueue is a min-heap. Each entry is an int[]{elevation, row, column} ordered with Integer.compare on the elevation.

Java

import java.util.PriorityQueue;

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        boolean[][] seen = new boolean[n][n];
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.add(new int[] {grid[0][0], 0, 0});
        seen[0][0] = true;
        int t = 0;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int h = top[0], r = top[1], c = top[2];
            t = Math.max(t, h);
            if (r == n - 1 && c == n - 1) return t;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= n || nc >= n || seen[nr][nc]) continue;
                seen[nr][nc] = true;
                heap.add(new int[] {grid[nr][nc], nr, nc});
            }
        }
        return t;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.swimInWater(new int[][] {{0, 2}, {1, 3}}));
        int[][] big = {
            {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}
        };
        System.out.println(s.swimInWater(big));
        System.out.println(s.swimInWater(new int[][] {{0}}));
    }
}

Output

3
16
0

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

How to explain it in an interview

Say first: binary search the time t and BFS over cells with elevation <= t; feasibility is monotonic, so that is O(n^2 log n).
Key insight: the cost of a path is its highest cell, so this is Dijkstra where "distance" is the maximum along the path instead of the sum.
Code it in steps: (1) a min-heap of {elevation, r, c} seeded with the start; (2) pop, update t = max(t, elevation); (3) stop when you pop the bottom-right; (4) push unseen in-bounds neighbours.
Complexity to state: time O(n^2 log n), space O(n^2).
Likely follow-ups / pitfalls: "why is the first pop of the target optimal?" (the heap always expands the lowest reachable cell, so nothing cheaper is left); mark cells seen when pushed to avoid duplicates; the start cell's own elevation counts.