To calculate trapped rainwater, we can use a two-pointer approach. Initialize left and right pointers at the beginning and end of the height array, respectively. Also, keep track of the maximum height encountered from the left (leftMax) and from the right (rightMax).
Iterate while the left pointer is less than the right pointer. In each step, compare leftMax and rightMax.
If leftMax is smaller, it means the water level is limited by the left side. Move the left pointer one step to the right. Update leftMax to be the maximum of its current value and the height at the new left pointer. The trapped water at this position is leftMax - height[left]. Add this to the total trapped water.
If rightMax is smaller or equal, the water level is limited by the right side. Move the right pointer one step to the left. Update rightMax to be the maximum of its current value and the height at the new right pointer. The trapped water at this position is rightMax - height[right]. Add this to the total trapped water.
Continue this process until the pointers meet. The accumulated sum represents the total trapped rainwater.
Adobe
Amazon
AppleCCitadel
Goldman Sachs
Intel