Rainwater in the Ruins — Solution & Editorial

Back to the Problem

Water above cell i is min(max height to the left, to the right) − h_i. Two pointers from both ends advance the side with the lower wall, maintaining running maxima — one pass, O(1) memory.

Complexity: O(N)

Watch out: ~10¹⁴ units of water at the limits — 64-bit.