LeetCode 778: Swim In Rising Water — Step-by-Step Visual Trace

#python #leetcode #algorithms

Hard — Binary Search | Depth-First Search | Matrix | Graph

The Problem

Find the minimum time required to swim from the top-left corner to the bottom-right corner of a grid, where each cell has a water level and you can only move when the current time is at least the water level of the cell.

Approach

Uses binary search on the answer combined with DFS to check feasibility. For each potential time value, performs DFS to verify if a path exists from start to end using only cells with water levels not exceeding that time.

Time: O(N^2 * log(N^2)) · Space: O(N^2)

Code

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        def dfs(i, j, visited, time):
            if i < 0 or i >= N or j < 0 or j >= N or visited[i][j] or grid[i][j] > time:
                return False
            if i == N - 1 and j == N - 1:
                return True
            visited[i][j] = True
            return (
                dfs(i + 1, j, visited, time)
                or dfs(i - 1, j, visited, time)
                or dfs(i, j + 1, visited, time)
                or dfs(i, j - 1, visited, time)
            )

        N = len(grid)
        left, right = 0, N * N

        while left < right:
            mid = (left + right) // 2
            visited = [[False] * N for _ in range(N)]
            if dfs(0, 0, visited, mid):
                right = mid
            else:
                left = mid + 1

        return left