Rain water trapping Leetcode optimize solution

Move the lower boundary

Set left = 0, right = n - 1, with leftMax and rightMax zero. While left < right, compare height[left] and height[right]. If the left height is smaller, update leftMax; otherwise add leftMax - height[left] and advance left. Symmetrically, when right is smaller, update rightMax, add its deficit, and decrement right. The lower boundary is decisive because the other side already has a wall at least that high, so its eventual maximum cannot reduce the water justified on the lower side. This is O(n) time and O(1) extra space; prefix/suffix maxima is an O(n)-space baseline. Test empty input, fewer than three bars, monotonic heights, equal heights, and large totals requiring a wide accumulator.