29. Trapping Rain Water

Given the heights of bars in an elevation map (width 1 each), compute how much water would be trapped between them after rain. Print that total volume.

Input: The first line contains n, the number of bars. The second line contains n space-separated non-negative integers representing bar heights. Output: Print a single integer - the total volume of water trapped.

1 <= n <= 10^5

A bar's OWN height never contributes negatively - if a bar is taller than both surrounding maximums (impossible by definition, since it IS one of them) or taller than the shorter side, it simply traps zero water at that position, never a negative amount.

Given a skyline of bars with different heights, figure out how much water would pool between them if it rained. Brute force: For every single bar, scan LEFT to find the tallest bar so far, and scan RIGHT to find the tallest bar so far, directly - this works but costs O(n) work per bar, giving O(n²) overall, which is slow for long skylines. Optimised: Instead of re-scanning left and right for every single bar, PRECOMPUTE the running max-from-left and max-from-right ONCE each (two simple linear passes), then look up both instantly for every bar - this collapses the O(n²) brute force into a clean O(n) solution.

Use two pointers starting at the array's two ends, tracking a running leftMax and rightMax as they move inward; at each step advance whichever pointer currently has the smaller running maximum, since that side's maximum is guaranteed to be the true limiting wall for water above its position regardless of what lies past the other pointer, so its trapped water can be added immediately and safely. This computes the identical total as the two-array version but tracks only two scalar maxima instead of storing a full array for each side. Time: O(n) Space: O(1)

For every bar i, separately scan all bars to its left to find the tallest one there and all bars to its right to find the tallest one there; the water sitting above bar i is the smaller of those two maxima minus the bar's own height (if positive), and summing this over every i gives the total trapped water. This is correct but each bar triggers two fresh linear scans across the entire array. Time: O(n^2) Space: O(1)

In one left-to-right pass, compute an array leftMax[i] holding the tallest bar from the start through i; in one right-to-left pass, compute rightMax[i] holding the tallest bar from i through the end. A third pass then sums min(leftMax[i], rightMax[i]) - height[i] for every bar, reusing the precomputed boundary maxima instead of rescanning for every single bar. Time: O(n) Space: O(n)

1. For every single bar, the water level ABOVE it is limited by whichever is SHORTER: the tallest bar anywhere to its left, or the tallest bar anywhere to its right. 2. Precompute, for every position, the tallest bar seen so far scanning from the left. 3. Precompute, for every position, the tallest bar seen so far scanning from the right. 4. For each position, the trapped water there is the SHORTER of those two maximums, minus the bar's own height (never negative) - sum this across every position.

Time: O(n) - two precomputation passes plus one final summation pass, all linear in the number of bars. Space: O(n), for the two precomputed max-from-left and max-from-right arrays (though a more advanced two-pointer variant can reduce this to O(1) extra space).

n = 1 or n = 2 (no water can ever be trapped); a strictly increasing or strictly decreasing height sequence (0 trapped); and n = 10^5 (largest, confirming the precomputed left/right max approach is O(n)).

This is one of the most iconic, frequently-asked array problems in technical interviews - be ready to explain the 'shorter of the two sides' insight clearly, since it's the entire crux of the problem.