Tech Blogs LLD SDE Playbook DSA

Swim in Rising Water

Hard Top 250
Associated Patterns
Graphs Heap & Priority Queue
Interviewed At (Company Tags)
GoogleAmazon
External Reference View on LeetCode

Problem Description

You are given an n x n integer grid 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 both elevations and the rain depth are at most t. You can swim infinite distances in zero time. Of course, you must start at the top left square (0, 0) and you can only swim when both the start and end squares are covered in water.

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:

Input: grid = [[0,2],[1,3]] Output: 3 Explanation: At time 0, you are at (0,0). You cannot go anywhere because grid[0][1] = 2 and grid[1][0] = 1. At time 1, you can swim to (1,0) but not to (1,1) since grid[1][1] = 3. At time 3, you can swim to (1,1). The path is (0,0) -> (1,0) -> (1,1). The maximum elevation on this path is 3, which is the answer.

Example 2:

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

Constraints

  • n == grid.length
  • n == grid[i].length
  • 1 ≤ n ≤ 50
  • 0 ≤ grid[i][j] < n²
  • All the values of grid[i][j] are unique permutations of grid cells.

Dijkstra: Minimize the Maximum Elevation Along Path

The problem asks for the path from (0, 0) to (n - 1, n - 1) that minimizes the maximum cell elevation encountered along the path.

This can be solved using Dijkstra’s algorithm:

  • Let time[r][c] be the minimum time to reach cell (r, c). Initialize time array with infinity, and time[0][0] = grid[0][0].
  • Use a min-heap to store [timeToCell, r, c], sorted by timeToCell. Seed the heap with [grid[0][0], 0, 0].
  • While the heap is not empty, pop the element [t, r, c] with the smallest time.
    • If r == n - 1 and c == n - 1, we can return t immediately.
    • If t > time[r][c], skip it.
    • For each of the 4-directional neighbors (nr, nc):
      • The time required to step into neighbor (nr, nc) is nextTime = max(t, grid[nr][nc]).
      • If nextTime < time[nr][nc], update time[nr][nc] = nextTime and push [nextTime, nr, nc] to the heap.

Solution: Modified Dijkstra

import java.util.*;

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] time = new int[n][n];
        for (int[] row : time) Arrays.fill(row, Integer.MAX_VALUE);
        time[0][0] = grid[0][0];

        // min-heap: [timeNeeded, r, c]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.offer(new int[]{grid[0][0], 0, 0});

        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

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

            if (r == n - 1 && c == n - 1) return t;
            if (t > time[r][c]) continue;

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                    int nextTime = Math.max(t, grid[nr][nc]);

                    if (nextTime < time[nr][nc]) {
                        time[nr][nc] = nextTime;
                        heap.offer(new int[]{nextTime, nr, nc});
                    }
                }
            }
        }

        return 0;
    }
}
import heapq

class Solution:
    def swimInWater(self, grid: list[list[int]]) -> int:
        n = len(grid)
        time = [[float('inf')] * n for _ in range(n)]
        time[0][0] = grid[0][0]

        # min-heap: (time_needed, r, c)
        heap = [(grid[0][0], 0, 0)]
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while heap:
            t, r, c = heapq.heappop(heap)

            if r == n - 1 and c == n - 1:
                return t
            if t > time[r][c]:
                continue

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    next_time = max(t, grid[nr][nc])

                    if next_time < time[nr][nc]:
                        time[nr][nc] = next_time
                        heapq.heappush(heap, (next_time, nr, nc))

        return 0
#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    int swimInWater(std::vector<std::vector<int>>& grid) {
        int n = grid.size();
        std::vector<std::vector<int>> time(n, std::vector<int>(n, 1e9));
        time[0][0] = grid[0][0];

        // min-heap: {timeNeeded, {r, c}}
        using T = std::pair<int, std::pair<int, int>>;
        std::priority_queue<T, std::vector<T>, std::greater<T>> heap;
        heap.push({grid[0][0], {0, 0}});

        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!heap.empty()) {
            auto [t, cell] = heap.top(); heap.pop();
            int r = cell.first, c = cell.second;

            if (r == n - 1 && c == n - 1) return t;
            if (t > time[r][c]) continue;

            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                    int nextTime = std::max(t, grid[nr][nc]);

                    if (nextTime < time[nr][nc]) {
                        time[nr][nc] = nextTime;
                        heap.push({nextTime, {nr, nc}});
                    }
                }
            }
        }

        return 0;
    }
};

Complexity Analysis:

  • Time Complexity: O(N² log N). Standard Dijkstra’s over N² states.
  • Space Complexity: O(N²) to store the time grid and heap elements.

← All Problems