Computes how much water is trapped between bars of an elevation map. Two pointers walk inward from both ends, resolving the shorter side first since its limiting wall is already known.
Computes how much water is trapped between bars of an elevation map. Two pointers walk inward from both ends, resolving the shorter side first since its limiting wall is already known.
Time complexity: O(n). Space complexity: O(1).
Core idea — Water above a bar is capped by the shorter of the tallest wall to its left and the tallest to its right. Two pointers track those running maxima from each end.
What each pass accomplishes — Whichever side currently has the shorter bar is safe to settle: its bounding wall on that side is already final. Add (sideMax − barHeight) units of water there and move that pointer inward. Each bar is resolved exactly once.
Use the interactive visualizer above to run Trapping Rain Water on your own input and watch every comparison, swap, and operation animate step by step — pause, scrub, or replay at any speed.