Swim in Rising Water

XXX. Swim in Rising Water

Graph

Priority Queue

Problem Statement:

You are given an n x n integer matrix grid where each value represents the water level at that cell. Starting from the top-left cell, your goal is to reach the bottom-right cell while minimizing the maximum water level encountered on the path.

Return the minimum time required to reach the bottom-right cell.

Algorithm:

1. Use a priority queue (min-heap) to always process the cell with the minimum water level first.
2. Initialize the priority queue with the starting cell (0, 0), storing the water level, row, and column indices.
3. Use a 2D boolean array to track visited cells to avoid re-processing.
4. At each step, pop the cell with the lowest water level from the queue, and update the maximum water level encountered so far.
5. If the bottom-right cell is reached, return the maximum water level encountered.
6. For each neighboring cell that is within bounds and not visited, add it to the priority queue.

Complexity:

Time Complexity: O(n² log n), where n is the grid size. Each cell is processed once, and heap operations take O(log n²) = O(2 log n).
Space Complexity: O(n²), for the priority queue and visited array.

Java Implementation:

import java.util.*;

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n]; // Track visited cells
        PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // Min-heap

        // Directions for moving up, down, left, right
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxTime = 0;

        // Start from the top-left cell
        pq.offer(new int[]{grid[0][0], 0, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll(); // Get the cell with the lowest water level
            int time = current[0], i = current[1], j = current[2];

            maxTime = Math.max(maxTime, time); // Update the maximum water level encountered

            // If bottom-right cell is reached, return the result
            if (i == n - 1 && j == n - 1) return maxTime;

            visited[i][j] = true; // Mark current cell as visited

            // Explore all valid neighbors
            for (int[] dir : directions) {
                int newI = i + dir[0], newJ = j + dir[1];
                if (newI >= 0 && newI < n && newJ >= 0 && newJ < n && !visited[newI][newJ]) {
                    pq.offer(new int[]{grid[newI][newJ], newI, newJ});
                }
            }
        }

        return -1; // Should not reach here if input guarantees a path
    }
}

Python Implementation:

import heapq

def swimInWater(grid):
    n = len(grid)
    visited = [[False] * n for _ in range(n)] # Track visited cells
    pq = [] # Min-heap

    # Directions for moving up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    max_time = 0

    # Start from the top-left cell
    heapq.heappush(pq, (grid[0][0], 0, 0))

    while pq:
        time, i, j = heapq.heappop(pq) # Get the cell with the lowest water level

        max_time = max(max_time, time) # Update the maximum water level encountered

        # If bottom-right cell is reached, return the result
        if i == n - 1 and j == n - 1:
            return max_time

        visited[i][j] = True # Mark current cell as visited

        # Explore all valid neighbors
        for di, dj in directions:
            new_i, new_j = i + di, j + dj
            if 0 <= new_i < n and 0 <= new_j < n and not visited[new_i][new_j]:
                heapq.heappush(pq, (grid[new_i][new_j], new_i, new_j))

    return -1 # Should not reach here if input guarantees a path

C++ Implementation:

#include 
#include 
#include 
#include 
using namespace std;

int swimInWater(vector>& grid) {
    int n = grid.size();
    vector> visited(n, vector(n, false)); // Track visited cells
    priority_queue, vector>, greater<>> pq; // Min-heap

    // Directions for moving up, down, left, right
    vector> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int max_time = 0;

    // Start from the top-left cell
    pq.emplace(grid[0][0], 0, 0);

    while (!pq.empty()) {
        auto [time, i, j] = pq.top();
        pq.pop(); // Get the cell with the lowest water level

        max_time = max(max_time, time); // Update the maximum water level encountered

        // If bottom-right cell is reached, return the result
        if (i == n - 1 && j == n - 1) return max_time;

        visited[i][j] = true; // Mark current cell as visited

        // Explore all valid neighbors
        for (auto [di, dj] : directions) {
            int new_i = i + di, new_j = j + dj;
            if (new_i >= 0 && new_i < n && new_j >= 0 && new_j < n && !visited[new_i][new_j]) {
                pq.emplace(grid[new_i][new_j], new_i, new_j);
            }
        }
    }

    return -1; // Should not reach here if input guarantees a path
}