# ============================================================================= # Solution: Swim in Rising Water # Difficulty: Hard | Pattern: BS + BFS # Link: https://leetcode.com/problems/swim-in-rising-water/ # ============================================================================= from typing import List import heapq # ============================================================================= # BRUTE FORCE -- O(n^2 * log(n^2)) Time, O(n^2) Space (Binary Search + BFS) # ============================================================================= # Binary-search the answer t; for each t, BFS to see if (0,0) -> (n-1,n-1) # is reachable using only cells <= t. class BruteForceSolution: def swimInWater(self, grid: List[List[int]]) -> int: n = len(grid) from collections import deque def reachable(t): if grid[0][0] > t: return False q = deque([(0, 0)]) seen = {(0, 0)} while q: x, y = q.popleft() if (x, y) == (n - 1, n - 1): return True for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)): nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in seen and grid[nx][ny] <= t: seen.add((nx, ny)) q.append((nx, ny)) return False lo, hi = grid[0][0], n * n - 1 while lo < hi: mid = (lo + hi) // 2 if reachable(mid): hi = mid else: lo = mid + 1 return lo # ============================================================================= # OPTIMAL -- O(n^2 log n) Time, O(n^2) Space (Dijkstra-like priority queue) # ============================================================================= # Min-heap by elevation. The answer is the max elevation along the chosen # path; we always extend the frontier through the smallest available cell. class Solution: def swimInWater(self, grid: List[List[int]]) -> int: n = len(grid) heap = [(grid[0][0], 0, 0)] seen = {(0, 0)} while heap: t, x, y = heapq.heappop(heap) if (x, y) == (n - 1, n - 1): return t for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)): nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in seen: seen.add((nx, ny)) heapq.heappush(heap, (max(t, grid[nx][ny]), nx, ny)) return -1 # ============================================================================= # TEST CASES # ============================================================================= if __name__ == "__main__": s = Solution() assert s.swimInWater([[0,2],[1,3]]) == 3 assert s.swimInWater( [[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]] ) == 16 print("All tests passed!")