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 (n1,n1)(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 n21n^2 - 1.