Command Palette

Search for a command to run...

Hectal
Problem 26.6 · Shortest PathsHard

Swim in Rising Water

PatternDijkstra's Shortest PathUnion-FindBinary Search on the Answer

What it teaches: Bottleneck path on a grid: the time needed is the highest cell on the best route.

Practise it on judges as “Swim in Rising Water”.

The problem

At time t the water level is t, and you can swim between adjacent cells when both have elevation ≤ t. Return the earliest time you can get from the top-left to the bottom-right of the n × n grid.

Example 1

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

Constraints

  • 1 ≤ n ≤ 50
  • Values are a permutation of 0..n² − 1

Pattern clues in the wording

  • → Minimise the maximum value along a path

These clues point to Dijkstra's Shortest Path: Always expand the closest unfinished node from a min-heap; with non-negative weights, its distance is final.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int swimInWater(int[][] grid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

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

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Minimax Dijkstra · O(n² log n)
1

Minimax Dijkstra

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

Heap of (max elevation so far, r, c), starting with grid[0][0]. Pop the smallest; when the corner pops, that's the answer.

Approach 1
import java.util.*;

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

Verdict: Same as Path With Minimum Effort, with cell values as costs.

Before you submit

Edge cases and common mistakes

Test these inputs

  • 1 × 1 grid
  • Corner cell is the highest

Mistakes people make

  • Forgetting the starting cell's own elevation.

Interview

Follow-up questions

Why is marking cells when they're pushed safe here?