# 42. Trapping Rain Water

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

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

Example:

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

# Solution

Approach 1: two passes -- for each bar, calculate the height of bars it's bounded by on both directions. Essentially use two passes to store highest_bar_so_far from both sides. O(N) time, O(N) space.

Approach 2: stack -- keep a stack of decreasing/nonincreasing bar heights (indices). Upon seeing a higher bar, pop from the stack and calculate trapped water in between. O(N) time, O(N) space.

Approach 3: two pointers -- the tower of bars and the trapped rain water forms pyramid shape, so we can use 2 pointers to trace the area of the pyramid. O(N) time, O(1) space.

Approach 4: (Time Limit Exceeded) Calculate layer by layer.

# Code (Python)

Approach 1:

    def trap(self, height):
        if len(height) < 2:
            return 0
        highest_from_left = [height[0]]
        for i in range(1, len(height)):
            highest_from_left.append(max(height[i], highest_from_left[-1]))
        highest_from_right = [0 for _ in range(len(height) - 1)] + [height[-1]]
        for i in range(len(height) - 2, -1, -1):
            highest_from_right[i] = max(height[i], highest_from_right[i+1])
        total = 0
        for i in range(len(height)):
            total += min(highest_from_left[i], highest_from_right[i]) - height[i]
        return total

Approach 2:

    def trap(self, height):
        if len(height) < 2:
            return 0
        stack = []
        total = 0
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                # calc trapped water with height stack[-1] or higher
                base_height = height[stack.pop()]
                if not stack:
                    break # no water trapped if bar just popped isn't bounded on the left
                total += (i - stack[-1] - 1) * (min(height[stack[-1]], height[i]) - base_height)
            stack.append(i)
        return total

Approach 3:

    def trap(self, height):
        if len(height) < 2:
            return 0
        prev_elevation = 0
        left, right = 0, len(height) - 1
        area_pyramid = 0
        while left < right:
            while height[left] <= prev_elevation and left < right:
                left += 1 # can deduct height[left] here to save another pass at the end: sum(height)
            while height[right] <= prev_elevation and left < right:
                right -= 1
            elevation = min(height[left], height[right])
            if elevation == prev_elevation: # two pointers meet
                return area_pyramid - sum(height)
            else:
                area_pyramid += (right - left + 1) * (elevation - prev_elevation)
                prev_elevation = elevation
        return area_pyramid - sum(height) # two pointers meet on a single highest point

# Code (C++)

Approach 1:

// DP.
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;
        int leftMax[n];
        int rightMax[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i)
            leftMax[i] = std::max(leftMax[i-1], height[i]);
        rightMax[n-1] = height[n-1];
        for (int i = n-2; i >= 0; --i)
            rightMax[i] = std::max(rightMax[i+1], height[i]);
        int total = 0;
        for (int i = 0; i < n; ++i)
        {
            if (i-1 >= 0 && i+1 < n &&
                leftMax[i-1] > height[i] &&
                rightMax[i+1] > height[i])
                total += std::min(leftMax[i-1], rightMax[i+1]) - height[i];
        }
        return total;
    }
};

Approach 2:

// Stack.
class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int total = 0;
        for (int i = 0; i < height.size(); ++i)
        {
            while (!st.empty() && height[st.top()] <= height[i])
            {
                int j = st.top();
                st.pop();
                if (!st.empty())
                {
                    int h = std::min(height[st.top()], height[i]);
                    total += (h - height[j]) * (i - st.top() - 1);
                }
            }
            st.push(i);
        }
        return total;
    }
};

Approach 3:

// Two pointers.
class Solution {
public:
    int trap(vector<int>& height) {
        int head = 0;
        int tail = height.size() - 1;
        int headMax = head;
        int tailMax = tail;
        int total = 0;
        while (head <= tail)
        {
            if (height[headMax] < height[tailMax])
            {
                if (height[head] >= height[headMax])
                {
                    headMax = head;
                    head++;
                }
                else
                {
                    total += height[headMax] - height[head];
                    head++;
                }
            }
            else
            {
                if (height[tail] >= height[tailMax])
                {
                    tailMax = tail;
                    tail--;
                }
                else
                {
                    total += height[tailMax] - height[tail];
                    tail--;
                }
            }
        }
        return total;
    }
};

Approach 4:

// Time Limit Exceeded.
// Calculate layer by layer.
class Solution {
public:
    int trap(vector<int>& height) {
        int nonZeroCount = 2;
        int totalCount = 0;
        while (nonZeroCount > 1)
        {
            nonZeroCount = 0;
            int head = 0;
            int tail = 0;
            int minHeight = 0;
            for (int i = 0; i < height.size(); ++i)
            {
                if (height[i] > 0 && minHeight == 0)
                    minHeight = height[i];
                else if (height[i] > 0)
                    minHeight = std::min(minHeight, height[i]);
            }
            while (tail < height.size())
            {
                if (height[head] == 0)
                {
                    head++;
                }
                else if (head < tail && height[tail] > 0)
                {
                    totalCount += minHeight * (tail - head - 1);
                    height[head] -= minHeight;
                    nonZeroCount++;
                    head = tail;
                }
                tail++;
            }
            if (head < height.size() && height[head] > 0)
            {
                height[head] -= minHeight;
                nonZeroCount++;
            }
        }
        return totalCount;
    }
};