42. trapping rain water

November 26, 2023 · 132 words · 1 min read · tech, programming

problem statement

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

• The key insight is that, When both extremes are high, water traps between them. and the height of water is always going to be the lower of the two extremes. this is true even if there is something that is higher than the current one, in between.
• So, a two pointer search from both ends, moving the lower value forward will work.

class Solution {
public:
    int trap(vector<int>& height) {
        int lmax = INT_MIN, rmax = INT_MIN, l = 0, r = height.size()-1, res = 0;

        while (l<r){
            lmax = max(lmax, height[l]);
            rmax = max(rmax, height[r]);
            res += lmax<rmax?lmax-height[l++]:rmax-height[r--];
        }
        return res;
    }
};