Problem Statement

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

Additional information

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• 0 <= grid[i][j] < n^2
• Each value grid[i][j] is unique.

Example 1:

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

Output: 3

Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

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

Explanation: The final route is 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Binary Search + Depth-First Search (DFS)

Intuition

We are trying to find the minimum time t that allows us to travel from the start to the end. The possible values for t range from grid[0][0] up to n^2 - 1.

Because the connectivity strictly increases as time goes on (if you can reach the end at time t, you can definitely reach it at time t + 1), this creates a perfect monotonic condition for Binary Search.

We can guess a time t (the middle of our search range) and run a standard Depth-First Search (DFS). During the DFS, we only step on cells where the elevation is less than or equal to t. If the DFS successfully reaches the bottom-right corner, our guessed time t is valid! We then search the lower half of the range to see if an even smaller time works. If the DFS fails, we must increase t and search the upper half.

Algorithm

1. Store the dimension n of the grid.
2. Create a helper function can_reach(t):

• If grid[0][0] > t, return False immediately.
• Initialize a stack with [(0, 0)] and a visited set.
• While the stack is not empty, pop (r, c).
• If r == n - 1 and c == n - 1, return True (we reached the end).
• Explore 4 neighbors. If a neighbor is in bounds, unvisited, and its elevation is <= t, add it to the stack and visited set.
• If the stack empties, return False.

3. Set the binary search bounds: l = grid[0][0] and r = n * n - 1.
4. Initialize res = r.
5. While l <= r:

• Calculate mid = (l + r) // 2.

• If can_reach(mid) is True:

• Update res = mid.

• Try to find a smaller time: r = mid - 1.

• Else:

• We need more time: l = mid + 1.

6. Return res.

def swim_in_water(grid: list[list[int]]) -> int:
    n = len(grid)
    
    def can_reach(t):
        if grid[0][0] > t:
            return False
            
        visited = set([(0, 0)])
        stack = [(0, 0)]
        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        
        while stack:
            r, c = stack.pop()
            
            if r == n - 1 and c == n - 1:
                return True
                
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
                    if grid[nr][nc] <= t:
                        visited.add((nr, nc))
                        stack.append((nr, nc))
                        
        return False
        
    l, r = grid[0][0], n * n - 1
    res = r
    
    while l <= r:
        mid = (l + r) // 2
        if can_reach(mid):
            res = mid
            r = mid - 1
        else:
            l = mid + 1
            
    return res

Time & Space Complexity

• Time complexity: O(N^2 log N)

• Reason: The maximum possible time is N^2. Binary searching over this range takes log(N^2) steps, which simplifies to 2 * log(N) -> O(log N). Inside each step, we run a DFS that visits at most N^2 cells. This gives a total time of O(N^2 log N).

• Space complexity: O(N^2)

• Reason: The visited set and DFS recursion stack can grow up to the total number of cells in the grid, O(N^2).

Dijkstra's Algorithm (Min-Heap) - Optimal

Intuition

Instead of blindly guessing the time and seeing if a path works, we can build the optimal path dynamically. The bottleneck of any path is the cell with the maximum elevation on that specific route.

We can modify Dijkstra's Algorithm to keep track of the maximum elevation encountered so far. We use a Min-Heap to always expand our search from the cell that has the smallest maximum path elevation.

Starting from (0, 0), we look at its neighbors. The "cost" to reach a neighbor is the maximum between the current path's peak elevation and the neighbor's own elevation. Because the Min-Heap always pops the smallest available bottleneck, the very first time we pop the destination cell (n - 1, n - 1), we are mathematically guaranteed that it is the absolute lowest possible bottleneck required to get there!

Algorithm

1. Store the dimension n.
2. Initialize a min_heap containing a tuple representing (max_elevation_so_far, r, c). Start with [(grid[0][0], 0, 0)].
3. Initialize a visited set with the starting cell (0, 0).
4. While the min_heap is not empty:

• Pop t, r, c. (t represents the maximum elevation required to reach this cell).
• If r == n - 1 and c == n - 1, we reached the end! Return t.
• Iterate through the 4 neighboring cells.
• If a neighbor is within bounds and not in visited:
• Mark it as visited immediately.
• Calculate the required time for the neighbor: max(t, grid[nr][nc]).
• Push this new state into the min_heap.

def swim_in_water(grid: list[list[int]]) -> int:
    n = len(grid)
    # Heap stores tuples of (max_time_in_path, row, col)
    min_heap = [(grid[0][0], 0, 0)]
    visited = set([(0, 0)])
    directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    
    while min_heap:
        t, r, c = heapq.heappop(min_heap)
        
        # If we reached the bottom-right corner, return the time
        if r == n - 1 and c == n - 1:
            return t
            
        # Explore neighbors
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
                visited.add((nr, nc))
                # The bottleneck is the max between the current path's bottleneck and the neighbor's height
                heapq.heappush(min_heap, (max(t, grid[nr][nc]), nr, nc))
                
    return 0

Time & Space Complexity

• Time complexity: O(N^2 log N)

• Reason: In the worst case, we might push all N^2 cells into the Min-Heap. Popping and pushing from a heap of size N^2 takes O(log(N^2)) -> O(log N) time. Processing all cells results in O(N^2 log N). While mathematically similar to the Binary Search approach, this evaluates paths dynamically and generally processes far fewer nodes in practice.

• Space complexity: O(N^2)

• Reason: The Min-Heap and the visited set will store at most O(N^2) elements.