# 42. Trapping Rain Water
###### tags: `Two Pointer`, `Bloomberg`

Description:
Given `n` non-negative integers representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining.

**Example:**

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Explanation: The above elevation map (black section) is represented by:
              [0,1,0,2,1,0,1,3,2,1,2,1]. 
In this case, 6 units of rain water (blue section) are being 

Solution:

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, secMax = 0, total = 0;
        
        while (l < r) {
            int lower;
            // choose lower wall
            if (height[l] < height[r]) {
                lower = height[l++];
            } else {
                lower = height[r--];
            }
            
            // the number of water that could be store will be decided by the max height wall
            secMax = Math.max(lower, secMax);
            total += secMax - lower;
        }
        return total;
    }
}

Time: O(n)
Space: O(1)

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int secMax = 0;
        int sum = 0;
        while (l < r) {
            int lower;
            if (height[l] < height[r]) {
                lower = height[l++];
            } else {
                lower = height[r--];
            }
            
            secMax = Math.max(secMax, lower);
            sum += secMax - lower;
        }
        return sum;
    }
}