Swim in Rising Water

1. Problem & Core Objective

Given an n × n grid where grid[r][c] is the elevation of that cell, water rises over time. At time t you may swim between adjacent cells if both elevations are <= t. Starting at (0,0), return the least time to reach (n−1, n−1).

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: 2 <= n <= 50 · elevations are a permutation of 0 .. n²−1

What's actually being tested: recognising that the path cost is a maximum, not a sum — and that Dijkstra works with any cost function that's monotonically non-decreasing along a path, not just addition. That generalisation is the insight; most people only meet Dijkstra with sums.

2. First-Principles Thought Process

What the answer actually measures

A path is swimmable at time t exactly when every cell on it has elevation <= t. So the time a given path becomes usable is the maximum elevation along it.

The answer is therefore:

the minimum, over all paths, of the maximum elevation on that path

That's a minimax path — sometimes called the bottleneck shortest path.

Why this isn't a normal shortest path

The cost of extending a path isn't cost + weight, it's max(cost, weight). Distance doesn't accumulate; it ratchets.

So Dijkstra's usual relaxation dist[v] = dist[u] + w becomes dist[v] = max(dist[u], elevation[v]).

Why Dijkstra still works

Dijkstra's correctness needs one property: extending a path never decreases its cost. Then the first pop of a node is final, because every alternative route already costs at least as much and can only grow.

max(a, b) >= a — so extending a path never reduces its maximum. The property holds, and Dijkstra applies unchanged apart from the relaxation formula.

That's worth stating explicitly, because it shows Dijkstra isn't about addition; it's about monotonicity.

The alternative: binary search the answer

Ask "is the destination reachable at time t?" — a plain BFS or DFS over cells with elevation <= t. That predicate is monotonic: if reachable at t, reachable at any larger t.

So binary search t over 0 .. n²−1, with an O(n²) reachability check per guess: O(n² log n²) = O(n² log n).

Same asymptotics as Dijkstra here, and it's the cleaner answer if the minimax framing doesn't come to mind.

3. Solution Paths

Approach 1 — Binary search on the answer plus a reachability check

public int swimInWater(int[][] grid) {
    int n = grid.length;
    int lo = grid[0][0], hi = n * n - 1;          // can't be less than the start's elevation

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canReach(grid, mid)) hi = mid;         // t works — try smaller
        else                     lo = mid + 1;
    }
    return lo;
}

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[]> stack = new ArrayDeque<>();
    stack.push(new int[]{0, 0}); seen[0][0] = true;

    while (!stack.isEmpty()) {
        int[] cell = stack.pop();
        if (cell[0] == n - 1 && cell[1] == n - 1) return true;
        for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {
            int nr = cell[0] + d[0], nc = cell[1] + d[1];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            if (seen[nr][nc] || grid[nr][nc] > t) continue;
            seen[nr][nc] = true;
            stack.push(new int[]{nr, nc});
        }
    }
    return false;
}

• Time O(n² log n) · Space O(n²)

Counter-questions on this approach

⭐ "Why is binary search valid here — what's the monotone predicate?"

"Reachable at time t" is monotone in t: if a path exists at time t, every cell on it has elevation <= t <= t', so the same path works at any larger t'. Reachability never turns off as the water rises.

That gives the false…false, true…true shape binary search needs — the same "search the answer space" pattern as Koko Eating Bananas.

⭐ "Why does lo start at grid[0][0] rather than 0?"

Because you begin standing on the start cell, so the time can never be below its elevation. Starting at 0 still converges to the right answer but wastes iterations on provably-false guesses.

Note the answer is also at least grid[n-1][n-1] for the same reason — seeding lo with the max of the two corners is slightly tighter.

"Why hi = n*n - 1?"

Elevations are a permutation of 0 .. n²−1, so that's the largest possible value and therefore an upper bound on the answer — at that time every cell is swimmable.

"Is this worse than Dijkstra?"

Same O(n² log n), different constant. Binary search does log(n²) full traversals; Dijkstra does one traversal with log per heap operation. In practice Dijkstra is usually a bit faster, but this version is easier to derive and reason about.

I'd offer whichever came to mind first and mention the other.

Approach 2 — Dijkstra with a max-based relaxation (optimal)

private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

public int swimInWater(int[][] grid) {
    int n = grid.length;
    boolean[][] visited = new boolean[n][n];
    PriorityQueue<int[]> heap =                          // {time, row, col}
        new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));

    heap.offer(new int[]{grid[0][0], 0, 0});
    visited[0][0] = true;

    while (!heap.isEmpty()) {
        int[] top = heap.poll();
        int time = top[0], r = top[1], c = top[2];

        if (r == n - 1 && c == n - 1) return time;        // first arrival is optimal

        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            if (visited[nr][nc]) continue;

            visited[nr][nc] = true;
            heap.offer(new int[]{Math.max(time, grid[nr][nc]), nr, nc});   // MAX, not sum
        }
    }
    return -1;                                            // unreachable on a full grid
}

Trace — grid = [[0,2],[1,3]]:

• Time O(n² log n) · Space O(n²)

Counter-questions on this approach

⭐ "Why does max work where Dijkstra normally uses +?"

Because Dijkstra's correctness doesn't depend on addition — it depends on the path cost being monotonically non-decreasing as you extend the path. That's what makes "the first pop is final" true: every alternative route already costs at least as much and can only grow further.

max(a, b) >= a, so extending a path never lowers its maximum. The property holds, and only the relaxation formula changes.

This generalises: Dijkstra works for any cost combiner that's monotone and associative in the right way — sum, max, and multiplication of probabilities in [0,1] (inverted) all qualify.

⭐ "Why mark visited on offer rather than on pop?"

To keep the heap at O(n²) entries rather than letting a cell be offered from all four neighbours.

It's safe only because the first offer of a cell is already its optimal time. With sum-based Dijkstra that isn't true — a later, cheaper route can appear — which is why the standard version uses lazy deletion instead.

Here the max-based cost from a popped node is already minimal for that neighbour, since the popped node's time is final. So marking on offer is correct, and it's worth explaining rather than copying.

⭐ "Why return on the first pop of the destination?"

Same finality argument. When the destination is popped with time t, every unexplored route costs at least t and can only increase. So t is the minimum.

Returning on offer would be wrong — the cell might be offered at a high time from one direction before a cheaper route is discovered.

"What does time represent at a given cell?"

The minimum over all paths from the start to that cell of the maximum elevation on the path. Not a distance, not a sum — the bottleneck.

"Could the grid be unreachable?"

Not with these constraints — the grid is full and four-connected, so every cell is reachable at a high enough time. The return -1 documents the precondition rather than handling a real case.

"Why is visited[0][0] = true set before the loop?"

So the start isn't re-offered from a neighbour later. Without it the start could be pushed again with a higher time, wasting a heap entry — harmless but sloppy.

Comparison

Both are optimal here; neither dominates.

4. Why the Optimal Wins

Neither strictly beats the other — same complexity, different framing, and both are good answers.

The Dijkstra version is the more transferable insight: it shows the algorithm isn't about summing weights, it's about a cost function that never decreases along a path. That reframing unlocks minimax paths, maximum-capacity paths, and probability-product paths, none of which are additive.

The binary search version is easier to derive under pressure and reuses the "search the answer space" pattern from Section 5.

The framing worth keeping:

The path cost here is a MAX, not a sum — so the answer is the minimum over paths of the maximum elevation. Dijkstra still applies, because its correctness needs only that extending a path never lowers its cost.

5. Java Prerequisites

Max-based relaxation

heap.offer(new int[]{Math.max(time, grid[nr][nc]), nr, nc});

Heap on a tuple's first element

new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));

Marking on offer vs on pop — safe here only because the first offer is already optimal. Sum-based Dijkstra needs lazy deletion instead.

Binary search on an answer space — lo = grid[0][0], hi = n*n - 1, with a monotone canReach(t) predicate. See Koko Eating Bananas.

6. Interview Communication Guide

Clarifying questions: Are diagonals allowed (no, four directions)? Are elevations distinct (yes — a permutation of 0..n²−1)? Is the start's elevation part of the cost (yes — you stand on it)? Is the destination always reachable (yes, on a full grid)?

The pitch

"A path becomes swimmable at the time equal to its maximum elevation, since every cell on it must be submerged. So the answer is the minimum over all paths of the maximum elevation — a minimax path.

The important realisation is that the cost doesn't accumulate. Extending a path isn't cost + weight, it's max(cost, elevation).

Dijkstra still works, and the reason is worth stating: its correctness doesn't depend on addition, it depends on the path cost being monotonically non-decreasing as you extend. That's what makes the first pop of a node final — every alternative already costs at least as much and can only grow.

And max(a, b) >= a, so the property holds. Only the relaxation formula changes.

One detail: I mark cells visited on offer rather than on pop, which keeps the heap at O(n²). That's safe here because the popped node's time is already final, so the max-based cost it offers a neighbour is already that neighbour's minimum. With sum-based Dijkstra it wouldn't be — a cheaper route could appear later — which is why the standard version uses lazy deletion.

O(n² log n).

There's an equally good alternative: binary search the answer. 'Is the destination reachable at time t?' is monotone in t, so binary search over 0..n²−1 with a BFS per guess — also O(n² log n). That's the easier derivation if the minimax framing doesn't come to mind, and it's the same search-the-answer-space pattern as Koko Eating Bananas."

Edge cases to volunteer:

Name the last row. It's where "sum" and "max" give visibly different answers, and it confirms the cost model was understood rather than copied from a standard Dijkstra template.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the path, not just the time."

Track a parent[][] updated when a cell is offered, then walk back from the destination. O(n²) extra space, no complexity change.

⭐ "Maximise the minimum elevation instead — a maximum-capacity path."

The mirror problem: relax with min(cost, elevation) and use a max-heap. The same monotonicity argument applies in reverse — extending never raises the minimum. This is the widest-path problem, used in network bandwidth routing.

"Use union-find instead."

Elegant here: sort cells by elevation and add them one at a time, unioning with already-added neighbours. The answer is the elevation at which (0,0) and (n−1,n−1) first become connected. O(n² α) after an O(n² log n) sort — and it's essentially Kruskal's building a minimum spanning tree, since the minimax path between two nodes runs along the MST.

"What if elevations could repeat?"

Nothing changes — the algorithm never relies on distinctness. Binary search would need care that the answer space is still the value range, but max and the monotone predicate both hold.

"What if n were 1000?"

n² = 10^6 cells, so O(n² log n) ≈ 2 × 10^7 — still fine. The heap holding a million int[3] objects is the memory concern; encoding (r,c) into a single int would help.

"Allow diagonal movement."

Eight offsets in DIRS. More routes become available, so the answer can only get smaller or stay equal. The algorithm is otherwise unchanged.