Trapping Rain Water
Given an elevation map as an array of non-negative bar heights (each of width one), compute how much water is trapped between the bars after rain.
- 1 ≤ n ≤ 2 · 10^4
- 0 ≤ height[i] ≤ 10^5
- Water above a bar = min(max to the left, max to the right) − height
- The smaller side's max is already final — safe to process it
- Opposite-direction pointers with running maxima
When order gives you a way to decide which of two ends to move, you can replace an O(n^2) double loop by a single pass. Opposite-direction pointers exploit sortedness (move the side that must change); same-direction pointers maintain a "written so far" prefix for in-place compaction.
Water over position i equals min(leftMax, rightMax) - height[i]. Use two pointers from the ends, each tracking the running maximum on its side. Whichever side has the smaller running maximum is fully determined (the other side is at least as tall), so add that side's trapped water and move its pointer inward. This computes the answer in one pass with no auxiliary arrays.
- Precompute left-max and right-max prefix arrays for an O(n) time, O(n) space solution. A monotonic stack fills water horizontally layer by layer, also in O(n).