Back to DSA

Trapping Rain Water

hard
Acceptance: 43%
StackMonotonic StackArray

You are given an array of non-negative integers that represent the height of bars in a cross-section. Each bar is one unit wide. Calculate the total volume of water that would be retained between the bars after rainfall. Solve this using a stack-based technique.

Examples

Example 1:
Input:height = [3,0,2,0,4]
Output:7
Example 2:
Input:height = [1,0,2,1,0,1,3]
Output:5

Hints

Related Problems

Min StackmediumValid ParentheseseasyEvaluate Reverse Polish NotationmediumDaily TemperaturesmediumNext Greater Element Ieasy
00:00
class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                water += leftMax - height[left];
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                water += rightMax - height[right];
                right--;
            }
        }
        return water;
    }
}
Time complexityO(n)
Space complexityO(n)