We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Swim in Rising Water

Number: 794

Difficulty: Hard

Paid? No

Companies: Google, Meta, DE Shaw, DoorDash, Uber, Amazon, PhonePe

Problem Description

Given an n x n grid where each cell represents an elevation, water rises over time so that at time t the water depth everywhere is t. Starting at the top-left cell (0, 0) you can move in four directions (up, down, left, right) to reach adjacent cells only if both current and destination cell elevations are ≤ t. The goal is to determine the minimum time required to reach the bottom-right cell (n - 1, n - 1).

Key Insights

  • The problem can be viewed as finding a path from the top-left to bottom-right where the cost is the maximum elevation encountered on that path.
  • A greedy approach using Dijkstra’s algorithm (or a min-heap based BFS) ensures that we always consider the next move with the smallest current elevation requirement.
  • Once the destination is reached, the maximum elevation along that path is the minimum time required.
  • Alternative approaches include binary search on time combined with a DFS/BFS check to see if a valid path exists.

Space and Time Complexity

Time Complexity: O(n^2 log(n^2)) which simplifies to O(n^2 log n) since each cell is processed once and we use a priority queue. Space Complexity: O(n^2) due to the visited matrix and the priority queue.

Solution

We can solve the problem using a min-heap based BFS (Dijkstra’s algorithm). Start at cell (0, 0) with its elevation as the initial cost, and use a min-heap to always expand the cell with the lowest required water level. For each popped cell, update the maximum elevation encountered on the current path. When reaching the target cell (n - 1, n - 1), this value represents the least time needed. We maintain a visited matrix to avoid reprocessing cells.

Code Solutions

import heapq

def swimInWater(grid):
    n = len(grid)
    # Initialize a visited set to track cells we have processed.
    visited = [[False] * n for _ in range(n)]
    # Min-heap: (current max elevation along the path, row, col)
    min_heap = [(grid[0][0], 0, 0)]
    visited[0][0] = True
    # Directions for moving up, down, left, and right.
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    
    while min_heap:
        time, r, c = heapq.heappop(min_heap)
        # If we reach the bottom-right, return the maximum elevation encountered along the path.
        if r == n - 1 and c == n - 1:
            return time
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Check boundaries and if the cell is not already visited.
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                visited[nr][nc] = True
                # The required time is the maximum of the current time and the elevation at the new cell.
                new_time = max(time, grid[nr][nc])
                heapq.heappush(min_heap, (new_time, nr, nc))
    
    return -1  # Should not reach here if input is as per constraints.

# Example Usage:
grid = [[0,2],[1,3]]
print(swimInWater(grid))  # Output: 3
← Back to All Questions