Trapping Rain Water

Problem

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.

Solution Approach

Find the maximum height $h_m$ and calculate the volume capacity for height $h_i$.

$Volume = (h_m - h_i)*(h_i)$

Take $h_i$ in the increasing order to avoid overlap problem. At the last, subtract the total volume occupy by the heights.

Expected Time complexity: $O(n)$

Click - to see solution code

C++

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int ans = 0, sm = height[0];
        int mx = height[0], indx = 0;
        for (int i = 1; i < n; i++) {
            sm += height[i];
            if (mx < height[i]) {
                mx = height[i];
                indx = i;
            }
        }
        mx = 0;
        ans = height[indx];
        for (int i = 0; i < indx; i++) {
            if (mx < height[i]) {
                ans += (indx - i) * (height[i] - mx);
                mx = height[i];
            }
        }
        mx = 0;
        for (int i = n - 1; i > indx; i--) {
            if (mx < height[i]) {
                ans += (i - indx) * (height[i] - mx);
                mx = height[i];
            }
        }
        return ans - sm;

    }
};