Data Structures19 sections · 729 units
Open in Course

Problem - Swimming in Rising Water

Union-Find with sorting

Given an n×nn \times n grid of elevations, find the minimum time tt such that you can swim from (0,0)(0,0) to (n−1,n−1)(n-1,n-1).

At time tt, you can swim to any cell with elevation ≤t\leq t. Water rises uniformly across the grid. Example:

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

At t=3t=3, all cells are reachable. Answer: 33.

This combines Union-Find with time-based activation. Constraints: nn from 11 to 5050, elevations from 00 to n2−1n^2 - 1.