778. Swim in Rising Water

Problem Statement

link: LeetCode.cn LeetCode

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

Example:

Input: grid = [[0,2],[1,3]] Output: 3

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^2 Each value grid[i][j] is unique.

Solution Approach

The solution uses a binary search combined with depth-first search (DFS) to find the minimum time t required to reach the bottom-right corner of the grid, starting from the top-left, where we search for the smallest t that allows for a path through cells with elevations less than or equal to t.

Algorithm

1. Binary Search on Time: We perform a binary search on the possible values of time t from the smallest elevation at the start to the largest elevation in the grid, aiming to find the minimum t that allows reaching the destination.2
2. DFS for Path Validation: For each midpoint t during the binary search, we use depth-first search (DFS) to check if there’s a path from the top-left to the bottom-right of the grid, only moving through cells with elevations less than or equal to t.
3. Termination Condition: The binary search terminates when the left and right bounds converge, and the resulting value of t is the minimum time required to reach the bottom-right corner of the grid.

Complexity

time complexity: O(n^2 log n) space complexity: O(n^2)

Implement

    class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        directions = [(0,1), (0,-1), (1,0), (-1,0)]
        
        def canReach(x, y, t, visited):
            if x == n - 1 and y == n - 1:
                return True
            visited[x][y] = True
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] <= t:
                    if canReach(nx, ny, t, visited):
                        return True
            return False

        left, right = grid[0][0], n * n - 1
        while left < right:
            mid = (left + right) // 2
            visited = [[False] * n for _ in range(n)]
            if canReach(0, 0, mid, visited):
                right = mid
            else:
                left = mid + 1
        
        return left

    
    

Twitter  facebook  Email