Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

778. Swim in Rising Water - Leetcode Solution

Code Implementation

import heapq

class Solution:
    def swimInWater(self, grid):
        N = len(grid)
        visited = [[False]*N for _ in range(N)]
        minHeap = [(grid[0][0], 0, 0)]  # (time, x, y)
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        while minHeap:
            time, x, y = heapq.heappop(minHeap)
            if x == N-1 and y == N-1:
                return time
            if visited[x][y]:
                continue
            visited[x][y] = True
            for dx, dy in directions:
                nx, ny = x+dx, y+dy
                if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                    heapq.heappush(minHeap, (max(time, grid[nx][ny]), nx, ny))
      
#include <vector>
#include <queue>
#include <utility>
using namespace std;

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int N = grid.size();
        vector<vector<bool>> visited(N, vector<bool>(N, false));
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        pq.emplace(grid[0][0], 0, 0);
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!pq.empty()) {
            auto [time, x, y] = pq.top(); pq.pop();
            if (x == N-1 && y == N-1) return time;
            if (visited[x][y]) continue;
            visited[x][y] = true;
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
                    pq.emplace(max(time, grid[nx][ny]), nx, ny);
                }
            }
        }
        return -1;
    }
};
      
import java.util.*;

class Solution {
    public int swimInWater(int[][] grid) {
        int N = grid.length;
        boolean[][] visited = new boolean[N][N];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{grid[0][0], 0, 0});
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int time = curr[0], x = curr[1], y = curr[2];
            if (x == N-1 && y == N-1) return time;
            if (visited[x][y]) continue;
            visited[x][y] = true;
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
                    pq.offer(new int[]{Math.max(time, grid[nx][ny]), nx, ny});
                }
            }
        }
        return -1;
    }
}
      
class MinHeap {
    constructor() {
        this.heap = [];
    }
    push([val, x, y]) {
        this.heap.push([val, x, y]);
        this._bubbleUp(this.heap.length - 1);
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._bubbleDown(0);
        return top;
    }
    _bubbleUp(i) {
        while (i > 0) {
            let p = Math.floor((i - 1) / 2);
            if (this.heap[p][0] <= this.heap[i][0]) break;
            [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
            i = p;
        }
    }
    _bubbleDown(i) {
        let n = this.heap.length;
        while (true) {
            let l = 2 * i + 1, r = 2 * i + 2, smallest = i;
            if (l < n && this.heap[l][0] < this.heap[smallest][0]) smallest = l;
            if (r < n && this.heap[r][0] < this.heap[smallest][0]) smallest = r;
            if (smallest === i) break;
            [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
            i = smallest;
        }
    }
    isEmpty() {
        return this.heap.length === 0;
    }
}

var swimInWater = function(grid) {
    const N = grid.length;
    const visited = Array.from({length: N}, () => Array(N).fill(false));
    const heap = new MinHeap();
    heap.push([grid[0][0], 0, 0]);
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    while (!heap.isEmpty()) {
        let [time, x, y] = heap.pop();
        if (x === N-1 && y === N-1) return time;
        if (visited[x][y]) continue;
        visited[x][y] = true;
        for (let [dx, dy] of dirs) {
            let nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
                heap.push([Math.max(time, grid[nx][ny]), nx, ny]);
            }
        }
    }
};

Problem Description

You are given an n x n integer matrix grid where each cell represents an elevation. Initially, the water level is at 0 and rises by 1 each unit of time. At time t, you can swim into a cell if its elevation is at most t. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (n-1, n-1) as early as possible. You can move up, down, left, or right to adjacent cells. Return the minimum time t such that you can reach (n-1, n-1).
  • Each move must be to an adjacent cell (no diagonal moves).
  • You cannot "reuse" a cell in the same path more than once.
  • There is exactly one valid solution for each input.

Thought Process

The challenge is to find the earliest time you can reach the destination, given that water rises and you can only step into a cell if the water has reached at least that cell's elevation. A brute-force approach would be to try all possible paths, but that would be very slow for larger grids. Instead, we can think of this as a shortest-path problem, where the "cost" to enter a cell is determined by the highest elevation encountered along the path so far. This is similar to Dijkstra's algorithm, where we always pick the next cell that can be reached at the lowest possible time. Using a priority queue (min-heap), we can always expand the path with the minimal maximum elevation, ensuring we find the optimal solution efficiently.

Solution Approach

To solve this problem efficiently, we use a modified Dijkstra's algorithm:
  1. Priority Queue (Min-Heap): We use a min-heap to always expand the cell that can be reached at the lowest possible time. Each entry in the queue is a tuple of (current_time, x, y), where current_time is the maximum elevation encountered so far on the path to (x, y).
  2. Visited Tracking: To avoid cycles and redundant work, we keep a visited matrix to mark cells we've already processed.
  3. Directions: For each cell, we attempt to move in all four directions (up, down, left, right), checking that the next cell is within bounds and not yet visited.
  4. Time Calculation: For each move, the time required to enter the next cell is the maximum of the current time and the elevation of the next cell (since you can't enter a cell until the water is at least at that elevation).
  5. Early Exit: As soon as we pop the destination cell from the heap, we return the current time, since by the nature of the heap, this is the earliest possible time to reach it.
This approach ensures that we always take the path that allows us to reach the end as soon as possible, efficiently pruning slower or impossible paths.

Example Walkthrough

Consider the following grid: 
  grid = [
    [0, 2],
    [1, 3]
  ]
  1. Start at (0,0) with elevation 0. Push (0, 0, 0) onto the heap.
  2. Pop (0, 0, 0). Adjacent cells are (1,0) (elevation 1) and (0,1) (elevation 2).
  3. Push (1, 1, 0) (max(0,1)=1) and (2, 0, 1) (max(0,2)=2).
  4. Pop (1, 1, 0). Adjacent cell (1,1) (elevation 3). Push (3, 1, 1) (max(1,3)=3).
  5. Pop (2, 0, 1). No new cells.
  6. Pop (3, 1, 1). This is the destination. Return 3.
The minimum time to reach the bottom-right is 3.

Time and Space Complexity

  • Brute-force: Would require exploring all possible paths, leading to exponential time complexity O(4^{N^2}) for an N x N grid, which is infeasible for large N.
  • Optimized (Dijkstra's): Each cell is pushed and popped at most once from the heap, and each heap operation takes O(\log(N^2)). Therefore, the total time complexity is O(N^2 \log N). Space complexity is O(N^2) for the visited matrix and the heap.

Summary

This problem is elegantly solved by viewing it as a shortest-path search with a custom "cost" function: the highest elevation encountered on a path. By always expanding the lowest-cost frontier using a priority queue (min-heap), we guarantee the earliest possible arrival at the destination. The approach is efficient, leverages classic graph algorithms, and avoids brute-force enumeration of all possible paths.