Swim in Rising Water

Hard Graphs Dijkstra Original on LeetCode

Reported atUber

Swim in Rising Water is a hard graphs problem solved with the dijkstra pattern. The best approach, optimal (dijkstra on the maximum elevation), runs in O(n² log n) time and O(n²) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every time) up.

Problem

You are given an n x n grid where grid[i][j] is the elevation of cell (i, j); all elevations are distinct numbers from 0 to n² - 1. Rain starts falling, and at time t the water level everywhere is t.

You start at the top-left cell (0, 0). At time t you may swim from a cell to any of its four neighbours, instantly and as far as you like, as long as both cells have elevation at most t. Return the earliest time at which you can reach the bottom-right cell (n - 1, n - 1).

Examples

Example 1

Input
grid = [[0, 3], [1, 2]]
Output
2
Why
Go down to 1 and then right to 2. Nothing higher than 2 is touched, and the target itself is 2.

Example 2

Input
grid = [[0, 5, 4], [8, 7, 3], [1, 2, 6]]
Output
6
Why
The route 0 -> 5 -> 4 -> 3 -> 6 never climbs above 6, and every route must end on the 6 anyway.

Example 3

Input
grid = [[3, 1, 6], [0, 8, 2], [4, 7, 5]]
Output
6
Why
Going along the top and down the right side, 3 -> 1 -> 6 -> 2 -> 5, peaks at 6; the left-side route through 0, 4, 7 would need time 7.

Constraints

  • n == grid.length == grid[i].length
  • 1 <= n <= 50
  • 0 <= grid[i][j] < n², and all values in the grid are distinct.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every time)O(n⁴)O(n²)
Better (binary search on time + BFS)O(n² log n)O(n²)
Optimal (Dijkstra on the maximum elevation)O(n² log n)O(n²)

1Brute force (try every time)

TimeO(n⁴)Up to n² values of t, each with a BFS over n² cells.
SpaceO(n²)The visited array and queue of one BFS.

Try t = 0, 1, 2, ... in order. For each t, run a BFS from (0, 0) that only steps onto cells with elevation <= t. The first t for which the target is reached is the answer.

  1. For t from max(grid[0][0], grid[n-1][n-1]) up to n² - 1:
  2. BFS from (0, 0) over 4-directional neighbours with elevation <= t.
  3. If (n - 1, n - 1) was visited, return t.
class Solution {
    private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        for (int t = Math.max(grid[0][0], grid[n - 1][n - 1]); ; t++) {
            if (canReach(grid, t)) return t;
        }
    }

    private boolean canReach(int[][] grid, int t) {
        int n = grid.length;
        boolean[][] seen = new boolean[n][n];
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[] { 0, 0 });
        seen[0][0] = true;
        while (!q.isEmpty()) {
            int[] c = q.poll();
            if (c[0] == n - 1 && c[1] == n - 1) return true;
            for (int[] d : DIRS) {
                int r = c[0] + d[0], col = c[1] + d[1];
                if (r >= 0 && r < n && col >= 0 && col < n && !seen[r][col] && grid[r][col] <= t) {
                    seen[r][col] = true;
                    q.add(new int[] { r, col });
                }
            }
        }
        return false;
    }
}

2Better (binary search on time + BFS)

TimeO(n² log n)About log(n²) BFS runs, each O(n²).
SpaceO(n²)Visited array and queue for one BFS.

Reachability only improves as t grows, so the predicate "the target is reachable at time t" is monotone. Binary search the smallest t in [max(start, target), n² - 1] and test each guess with a BFS.

  1. lo = max(grid[0][0], grid[n-1][n-1]), hi = n² - 1.
  2. While lo < hi: mid = (lo + hi) / 2; if BFS at mid reaches the target, hi = mid, else lo = mid + 1.
  3. Return lo.
class Solution {
    private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

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

    private boolean canReach(int[][] grid, int t) {
        int n = grid.length;
        boolean[][] seen = new boolean[n][n];
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[] { 0, 0 });
        seen[0][0] = true;
        while (!q.isEmpty()) {
            int[] c = q.poll();
            if (c[0] == n - 1 && c[1] == n - 1) return true;
            for (int[] d : DIRS) {
                int r = c[0] + d[0], col = c[1] + d[1];
                if (r >= 0 && r < n && col >= 0 && col < n && !seen[r][col] && grid[r][col] <= t) {
                    seen[r][col] = true;
                    q.add(new int[] { r, col });
                }
            }
        }
        return false;
    }
}

3Optimal (Dijkstra on the maximum elevation)

TimeO(n² log n)Each of the n² cells enters and leaves the heap once, at O(log n²) each.
SpaceO(n²)Visited array and heap.

Treat the cost of a path as the highest elevation on it. Starting from (0, 0), repeatedly pop the frontier cell with the lowest elevation from a min-heap, raise a running maximum to that elevation, and push its unvisited neighbours. Because the heap always grows the reachable region through the lowest possible cell, the running maximum when the target is popped is the minimum time.

  1. Push (grid[0][0], 0, 0) and mark (0, 0) visited; set best = 0.
  2. Pop the smallest cell; best = max(best, its elevation).
  3. If it is (n - 1, n - 1), return best.
  4. Push every unvisited neighbour and mark it visited.
class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        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 best = 0;
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            best = Math.max(best, cur[0]);
            if (cur[1] == n - 1 && cur[2] == n - 1) return best;
            for (int[] d : dirs) {
                int r = cur[1] + d[0], c = cur[2] + d[1];
                if (r >= 0 && r < n && c >= 0 && c < n && !seen[r][c]) {
                    seen[r][c] = true;
                    pq.offer(new int[] { grid[r][c], r, c });
                }
            }
        }
        return best;
    }
}

Edge cases to test

  • A 1 x 1 grid: the answer is the single value
  • The start cell or the target cell holds the largest value on the best route
  • The best route winds around a ridge instead of going straight

Hints

Hint 1

At time t you can stand on exactly the cells with elevation <= t. The answer is the smallest t for which the start and target are connected through such cells.

Hint 2

Being reachable at time t implies being reachable at t + 1, so you can binary search on t and run a BFS for each guess.

Hint 3

Even better: run Dijkstra where the cost of a path is the largest elevation on it. Always expand the reachable cell with the lowest elevation using a min-heap; when you pop the target, the running maximum is the answer.

FAQ

What is the best time complexity for Swim in Rising Water?

Optimal (Dijkstra on the maximum elevation) runs in O(n² log n) time and O(n²) extra space. Each of the n² cells enters and leaves the heap once, at O(log n²) each.

Which pattern does Swim in Rising Water use?

It is a graphs problem that uses the dijkstra pattern. Other problems with the same pattern: Network Delay Time, Find the City With the Smallest Number of Neighbors at a Threshold Distance, Cheapest Flights Within K Stops.

Is there a brute force solution for Swim in Rising Water?

Yes. Brute force (try every time) takes O(n⁴) time and O(n²) space. Try t = 0, 1, 2, ...

Which edge cases should I test for Swim in Rising Water?

A 1 x 1 grid: the answer is the single value; The start cell or the target cell holds the largest value on the best route; The best route winds around a ridge instead of going straight.