DiffPush Tier Graphs · MST Problems O(n^2 log n) · O(n^2)
A storm drain network floods continuously: at time t every cell whose elevation is at most t is submerged and swimmable. A maintenance diver launches from the intake corner and must reach the outlet corner, able to cross only when both cells sit under water. The dive plan needs the earliest clock time at which some route from corner to corner becomes fully swimmable.
Input: An n x n matrix grid where grid[i][j] is the elevation of cell (i, j); all elevations are distinct.
Output: Return the least time t at which the bottom-right cell becomes reachable from the top-left.
1 <= n <= 500 <= grid[i][j] < n^2All elevations are distinctInput: {"grid":[[0,2],[1,3]]}
Output: 3
The outlet's elevation 3 is the last gate on the only diagonal-adjacent route.
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
The snake route's deepest gate — elevation 16 — is the binding constraint.