Trapping Rain Water

You are given an array of n non-negative integers representing an elevation map where the width of each bar is 1. Compute the total volume of rainwater that would be trapped between the bars after raining, where the water level above any bar is bounded on each side by the tallest bar seen so far in that direction and cannot spill past the array's edges.

Input: The first line contains the integer n. The second line contains n space-separated non-negative integers representing height. Output: Print a single integer: the total units of water trapped.

1 <= n <= 10^5 0 <= height[i] <= 10^9

This is a significant space improvement over the more commonly-taught 'precompute left-max and right-max arrays' O(n)-space approach - recognizing that you don't need to know the FULL left/right max arrays upfront, just which side's running max is currently smaller at each step, is the key insight enabling O(1) space.

Compute how much rainwater an elevation map of bars can trap, using two pointers and running maximums from each side. Brute force: For every position, scan LEFT and RIGHT separately to find the tallest bar in each direction, then compute the trapped water there - this costs O(n²) in the worst case, or O(n) with PRECOMPUTED left-max and right-max arrays (using O(n) extra space), when a two-pointer approach achieves the same result with only O(1) extra space. Optimised: Since the water trapped at any position depends only on the SMALLER of its two-directional maximums, and you always advance whichever SIDE's running maximum is currently smaller (because that side's bound is already fully and correctly determined, regardless of what's further in the other direction), a single two-pointer pass with two running maximums computes the total trapped water in O(n) time and O(1) space - no precomputed arrays needed.

1. At any position, the water level above it is bounded by the SMALLER of the tallest bar to its LEFT and the tallest bar to its RIGHT. 2. Use two pointers at both ends together with two running maximums (leftMax, rightMax); always advance the side whose running maximum is SMALLER, since that side's bound is already fully determined. 3. When advancing the smaller side, the water trapped at that position is simply its running maximum MINUS its own height; accumulate that into a running total.

Time: O(n) - a single two-pointer pass through the array. Space: O(1) - just two pointers and two running maximums, no precomputed arrays.

Handle a strictly increasing or strictly decreasing elevation (traps zero water) and n = 1 (also always zero, since water needs a bar on both sides); use the two-pointer technique with 64-bit accumulation to stay within O(n) time and avoid overflow at n = 10^5 with heights up to 10^9.

Be ready to explain WHY advancing the side with the SMALLER running maximum is always safe - that side's water level is already fully determined (bounded by its own smaller maximum), regardless of what even taller bars might exist further away on the OTHER side.