Leetcode 42 Solution

This article provides solution to leetcode question 42 (trapping-rain-water)
Categories:
Tags:
Access this page by simply typing in "lcs 42" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/trapping-rain-water

Solution

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();



        if (n == 0)
            return 0;



        int a[n];
        int b[n];



        int total = 0;



        for (int i = 0; i < n; i++)
        {
            if (i == 0)
                a[i] = height[i];
            else
                a[i] = max(a[i - 1], height[i]);
        }



        for (int i = n - 1; i >= 0; i--)
        {
            if (i == n - 1)
                b[i] = height[i];
            else
                b[i] = max(b[i + 1], height[i]);
        }



        for (int i = 1; i < n - 1; i++)
        {
            total += max(min(a[i - 1], b[i + 1]) - height[i], 0);
        }



        return total;
    }
};