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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Swim in Rising Water

Difficulty: Hard

Problem Description

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).

Key Insights

  • The problem requires finding the minimum time t for which there exists a path from the top-left corner of the grid to the bottom-right corner that only traverses cells with elevations ≤ t.
  • A priority queue (min-heap) can be utilized to explore the minimum elevation paths first, similar to Dijkstra's algorithm.
  • The algorithm needs to check adjacent cells, ensuring that both the current cell and the adjacent cell elevations do not exceed t.

Space and Time Complexity

Time Complexity: O(n^2 log n) - Due to the use of a priority queue to explore each cell. Space Complexity: O(n^2) - For the visited matrix and the priority queue.

Solution

The solution involves using a priority queue to perform a modified Dijkstra's algorithm. We start from the top-left corner of the grid and explore the adjacent cells. We push each adjacent cell into the priority queue with its elevation as the priority. We continue this process until we reach the bottom-right corner. The maximum elevation we encounter on the path to (n-1, n-1) at the time we reach it will be our answer.

Code Solutions

import heapq

def swimInWater(grid):
    n = len(grid)
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    min_heap = [(grid[0][0], 0, 0)]  # (time, x, y)
    visited = set((0, 0))
    
    while min_heap:
        t, x, y = heapq.heappop(min_heap)
        if x == n - 1 and y == n - 1:
            return t
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited:
                visited.add((nx, ny))
                heapq.heappush(min_heap, (max(t, grid[nx][ny]), nx, ny))
← Back to All Questions