LeetEye LeetEye
Hard Advanced Graphs ~5 min

Swim in Rising Water

advanced-graphs swim-in-rising-water

Problem

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 is at most t.

Return the least time until you can reach the bottom right square (n - 1, n - 1) starting from the top left square (0, 0).

Examples

Example 1
Input: grid = [[0,2],[1,3]]
Output: 3
At time 3, we can swim anywhere.
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
Key Insight

This is "minimax path" - minimize the maximum edge weight. Use modified Dijkstra's.

Minimax path problem: Dijkstra's where we minimize the maximum elevation along the path. Priority = max elevation needed to reach each cell.

How to Approach This Problem

Pattern Recognition: When you see keywords like swim in rising water advanced-graphs, think Advanced Graphs.

Step-by-Step Reasoning

1 We can traverse a cell when:
Answer: Water level >= that cell's elevation
We can enter a cell only when water covers it.
2 The minimum time to reach destination:
Answer: Minimum of (maximum elevation) across all paths
We need water to cover the highest point on our path. We want the path with smallest "highest point".
3 For minimax path, use:
Answer: Dijkstra with max instead of sum
Dijkstra's greedy approach works - always expand the cell with minimum "max so far".
4 The min-heap should store:
Answer: (max_elevation_to_reach, position)
We prioritize by the maximum elevation needed to reach each cell.
5 When moving to neighbor, the new "cost" is:
Answer: max(current_cost, neighbor_elevation)
The cost to reach neighbor is the max of (cost to reach current, neighbor's elevation).

Solution

import heapq

def swimInWater(grid: List[List[int]]) -> int:
    n = len(grid)
    visited = set()
    min_heap = [(grid[0][0], 0, 0)]  # (max_elevation, row, col)
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while min_heap:
        max_elev, r, c = heapq.heappop(min_heap)
        
        if (r, c) in visited:
            continue
        
        visited.add((r, c))
        
        # Reached destination
        if r == n - 1 and c == n - 1:
            return max_elev
        
        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:
                # New cost is max of current max and neighbor's elevation
                new_max = max(max_elev, grid[nr][nc])
                heapq.heappush(min_heap, (new_max, nr, nc))
    
    return -1

Complexity Analysis

Time O(n² log n)
Space O(n²)

Master This Pattern

Build intuition with interactive MCQs. Practice Advanced Graphs problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye