Problem

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Examples

Example 1:

$$ \Huge \begin{array}{|c|c|} \hline 0 & 2 \\ \hline 1 & 3 \\ \hline \end{array} $$

1
2
3
4
5
6
7
8
9

Input:
grid = [[0,2],[1,3]]
Output:
 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

$$ \Huge \begin{array}{|c|c|c|c|c|} \hline \colorbox{Turquoise} 0 & \colorbox{Turquoise}1 & \colorbox{Turquoise}2 & \colorbox{Turquoise}3 & \colorbox{Turquoise}4 \\ \hline 24 & 23 & 22 & 21 & \colorbox{Turquoise}5 \\ \hline \colorbox{Turquoise}12 & \colorbox{Turquoise}13 & \colorbox{Turquoise}14 & \colorbox{Turquoise}15 & \colorbox{Turquoise}16 \\ \hline \colorbox{Turquoise}11 & 17 & 18 & 19 & 20 \\ \hline \colorbox{Turquoise}10 & \colorbox{Turquoise}9 &\colorbox{Turquoise} 8 & \colorbox{Turquoise}7 & \colorbox{Turquoise}6 \\ \hline \end{array} $$

1
2
3
4
5
6

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
Explanation: The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Solution

Method 1 – Dijkstra’s Algorithm

Intuition

We want to reach the bottom-right cell as soon as possible, but we can only move to a cell if the water level (time) is at least as high as the highest elevation we’ve seen so far on our path. Dijkstra’s algorithm is ideal for finding the minimum ‘maximum elevation’ path in a weighted grid.

Approach

  1. Use a min-heap (priority queue) to always expand the cell with the lowest current maximum elevation.
  2. Start from (0,0) with its elevation as the initial time.
  3. For each move, update the time to be the maximum of the current time and the elevation of the next cell.
  4. Mark cells as visited to avoid revisiting.
  5. When reaching (n-1, n-1), return the time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<bool>> vis(n, vector<bool>(n, false));
        priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
        pq.push({grid[0][0], 0, 0});
        vector<int> dx{0,0,1,-1}, dy{1,-1,0,0};
        while (!pq.empty()) {
            auto [t, x, y] = pq.top(); pq.pop();
            if (x == n-1 && y == n-1) return t;
            if (vis[x][y]) continue;
            vis[x][y] = true;
            for (int d = 0; d < 4; ++d) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny]) {
                    pq.push({max(t, grid[nx][ny]), nx, ny});
                }
            }
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func swimInWater(grid [][]int) int {
    n := len(grid)
    vis := make([][]bool, n)
    for i := range vis { vis[i] = make([]bool, n) }
    h := &hp{{grid[0][0], 0, 0}}
    heap.Init(h)
    dx := []int{0,0,1,-1}
    dy := []int{1,-1,0,0}
    for h.Len() > 0 {
        t, x, y := (*h)[0][0], (*h)[0][1], (*h)[0][2]
        heap.Pop(h)
        if x == n-1 && y == n-1 { return t }
        if vis[x][y] { continue }
        vis[x][y] = true
        for d := 0; d < 4; d++ {
            nx, ny := x+dx[d], y+dy[d]
            if nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny] {
                heap.Push(h, [3]int{max(t, grid[nx][ny]), nx, ny})
            }
        }
    }
    return -1
}
type hp [][3]int
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x any)        { *h = append(*h, x.([3]int)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        boolean[][] vis = new boolean[n][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{grid[0][0], 0, 0});
        int[] dx = {0,0,1,-1}, dy = {1,-1,0,0};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int t = cur[0], x = cur[1], y = cur[2];
            if (x == n-1 && y == n-1) return t;
            if (vis[x][y]) continue;
            vis[x][y] = true;
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny]) {
                    pq.offer(new int[]{Math.max(t, grid[nx][ny]), nx, ny});
                }
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun swimInWater(grid: Array<IntArray>): Int {
        val n = grid.size
        val vis = Array(n) { BooleanArray(n) }
        val pq = java.util.PriorityQueue(compareBy<Triple<Int,Int,Int>> { it.first })
        pq.add(Triple(grid[0][0], 0, 0))
        val dx = intArrayOf(0,0,1,-1)
        val dy = intArrayOf(1,-1,0,0)
        while (pq.isNotEmpty()) {
            val (t, x, y) = pq.poll()
            if (x == n-1 && y == n-1) return t
            if (vis[x][y]) continue
            vis[x][y] = true
            for (d in 0..3) {
                val nx = x + dx[d]
                val ny = y + dy[d]
                if (nx in 0 until n && ny in 0 until n && !vis[nx][ny]) {
                    pq.add(Triple(maxOf(t, grid[nx][ny]), nx, ny))
                }
            }
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def swimInWater(self, grid: list[list[int]]) -> int:
        n = len(grid)
        vis = [[False]*n for _ in range(n)]
        import heapq
        pq = [(grid[0][0], 0, 0)]
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        while pq:
            t, x, y = heapq.heappop(pq)
            if x == n-1 and y == n-1:
                return t
            if vis[x][y]: continue
            vis[x][y] = True
            for d in range(4):
                nx, ny = x+dx[d], y+dy[d]
                if 0 <= nx < n and 0 <= ny < n and not vis[nx][ny]:
                    heapq.heappush(pq, (max(t, grid[nx][ny]), nx, ny))
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn swim_in_water(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut vis = vec![vec![false; n]; n];
        let mut pq = BinaryHeap::new();
        pq.push(Reverse((grid[0][0], 0, 0)));
        let dx = [0,0,1,-1];
        let dy = [1,-1,0,0];
        while let Some(Reverse((t, x, y))) = pq.pop() {
            if x == n-1 && y == n-1 { return t; }
            if vis[x][y] { continue; }
            vis[x][y] = true;
            for d in 0..4 {
                let nx = x as i32 + dx[d];
                let ny = y as i32 + dy[d];
                if nx >= 0 && nx < n as i32 && ny >= 0 && ny < n as i32 {
                    let nx = nx as usize; let ny = ny as usize;
                    if !vis[nx][ny] {
                        pq.push(Reverse((t.max(grid[nx][ny]), nx, ny)));
                    }
                }
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    swimInWater(grid: number[][]): number {
        const n = grid.length;
        const vis: boolean[][] = Array.from({length: n}, () => Array(n).fill(false));
        const pq: [number, number, number][] = [[grid[0][0], 0, 0]];
        const dx = [0,0,1,-1], dy = [1,-1,0,0];
        while (pq.length) {
            pq.sort((a, b) => a[0] - b[0]);
            const [t, x, y] = pq.shift()!;
            if (x === n-1 && y === n-1) return t;
            if (vis[x][y]) continue;
            vis[x][y] = true;
            for (let d = 0; d < 4; d++) {
                const nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny]) {
                    pq.push([Math.max(t, grid[nx][ny]), nx, ny]);
                }
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 log n), as each cell is pushed/popped from the heap at most once, and heap operations take log(n^2).
  • 🧺 Space complexity: O(n^2), for the visited matrix and the heap.