Swim in Rising Water

Admit cells in height order; the answer is the link.

Monotone growth is the whole structure: the passable set at threshold t contains the passable set at every smaller threshold, so connectivity events happen ONCE and never un-happen. That licenses processing admissions as a single accumulating stream instead of per-level snapshots. Sort all cells by height; sweep the thresholds in that order; when a cell is admitted, it can only connect through neighbours ALREADY admitted (lower or equal height) — union it with each such neighbour. Connectivity is thereby maintained incrementally — union-find's exact contract, insertion-only — and after each admission one O(α) query asks: do the two corners share a root yet? The FIRST admission after which they do gives the answer: its height is the minimal viable water level, because at every smaller threshold the sweep had already admitted everything passable and the corners were still separate — the sweep IS the proof of minimality, an exhaustive check of all lower thresholds performed cumulatively rather than repeatedly. Recognise the lineage: this is Kruskal's algorithm with the destination changed — Kruskal admits edges in weight order until a spanning tree forms; here cells are admitted in height order until one specific pair connects. Both are instances of threshold connectivity: sort by the parameter, insert in order, stop at the connectivity event you care about. The bottleneck value of the minimax path (the largest height you're forced through) is exactly the threshold at the event — which reveals the kinship with Path With Minimum Effort: SAME minimax objective, and indeed modified Dijkstra (relax with max(pathMax, cellHeight)) solves this problem too, in the same O(mn log mn). The two files split the two unlocks deliberately: Dijkstra generalises the combiner; Kruskal-style sweep converts monotone-threshold questions into incremental union — and the sweep is the one that survives when the question is about connectivity events rather than per-node optima (e.g., 'when do ALL cells connect'). Binary search on t with a BFS feasibility check is the third valid route — the monotone yes/no line again — costing O(mn log maxHeight): worth naming because it needs no union-find and no Dijkstra proof, only the monotonicity observation.