Swim in Rising Water

Explanation & Solution

Description

You are given an n x n integer matrix grid where grid[i][j] represents the elevation at that position. At time t, the depth of the water everywhere is t.

You can swim from one cell to an adjacent (4-directional) cell in one step if and only if the maximum elevation along your path so far is at most t.

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

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

Output: 3

Explanation: At time 3 you can travel along path (0,0)→(1,0)→(1,1). The max elevation on this path is max(0,1,3)=3.

Constraints

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

Approach

K-way Merge pattern

1. Model as Dijkstra's Shortest Path

Define the "cost" to reach a cell as the maximum elevation on any path from (0,0) to that cell
We want to minimize this maximum — classic minimax path problem
Use a min-heap ordered by this cost, starting with (grid[0][0], 0, 0)

2. Greedy Extraction

Pop the cell with the smallest current maximum elevation
If already visited, skip (a shorter path was already found)
If it's the destination (n-1, n-1), return the cost immediately

3. Expand Neighbors

For each unvisited 4-directional neighbor (nr, nc), the path cost is Math.max(currentCost, grid[nr][nc])
Push this into the heap and sift up

4. Correctness

Because we always expand the cell with the minimum bottleneck cost first, the first time we reach the destination is guaranteed to be optimal

Key Insight

This is Dijkstra's algorithm where edge weight is max(current_cost, neighbor_elevation) instead of a sum — the heap always prioritizes the path with the smallest peak elevation

Time

O(n² log n²) = **O(n² log n)** — each cell is processed once

Space

O(n²) for the heap and visited array

Visualization

Input:

DFS Traversal2×2 grid

output—

Press play to start dfs traversal

CurrentQueuedVisitedSource

21 steps

Solution Code

Range Sum of Sorted Subarray Sums