Trapping Rain Water Solutions in C++

// Source : https://oj.leetcode.com/problems/trapping-rain-water/
// Author : Hao Chen
// Date   : 2014-07-02



#include <stdio.h>
/*
 * The idea is:
 *    1) find the highest bar.
 *    2) traverse the bar from left the highest bar.
 *       becasue we have the highest bar in right, so, any bar higher than its right bar(s) can contain the water.
 *    3) traverse the bar from right the highest bar.
 *       becasue we have the highest bar in left, so, any bar higher than its left bar(s) can contain the water.
 *
 * The code below is quite clear!
 *
 */
int trap(int a[], int n) {
    int result = 0;

    //find the highest value/position
    int maxHigh = 0;
    int maxIdx = 0;
    for(int i=0; i<n; i++){
        if (a[i] > maxHigh){
            maxHigh = a[i];
            maxIdx = i;
        }
    }

    //from the left to the highest postion
    int prevHigh = 0;
    for(int i=0; i<maxIdx; i++){
        if(a[i] > prevHigh){
            prevHigh = a[i];
        }
        result += (prevHigh - a[i]);
    }

    //from the right to the highest postion
    prevHigh=0;
    for(int i=n-1; i>maxIdx; i--){
        if(a[i] > prevHigh){
            prevHigh = a[i];
        }
        result += (prevHigh - a[i]);
    }

    return result;
}

#define TEST(a) printf("%d\n", trap(a, sizeof(a)/sizeof(int)))
int main()
{
    int a[]={2,0,2};
    TEST(a);
    int b[]={0,1,0,2,1,0,1,3,2,1,2,1};
    TEST(b);
    return 0;
}

#include <algorithm>

using std::max;

class Solution {
public:
    int trap(int A[], int n) {
        if (n<3) return 0;
        int count{0};
        for (int i=0, j=n-1, maxI=A[i], maxJ=A[j]; i<j; maxI=max(maxI, A[i]), maxJ=max(maxJ, A[j]))
            if (maxI < maxJ) count += maxI - A[i++];
            else count += maxJ - A[j--];
        return count;
    }
};

/// Source : https://leetcode.com/problems/trapping-rain-water/description/
/// Author : liuyubobobo
/// Time   : 2018-09-16

#include <iostream>
#include <vector>

using namespace std;


/// Brute Force
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    int trap(vector<int>& height) {

        if(height.size() <= 2)
            return 0;

        int res = 0;
        for(int i = 1; i < height.size() - 1; i ++) {
            int lmax = height[i], rmax = height[i];
            for (int l = i - 1; l >= 0; l --)
                lmax = max(lmax, height[l]);
            for(int r = i + 1; r < height.size(); r ++)
                rmax = max(rmax, height[r]);
            res += min(lmax, rmax) - height[i];
        }
        return res;
    }
};


int main() {

    vector<int> height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << Solution().trap(height1) << endl;
    // 6

    vector<int> height2 = {4,2,3};
    cout << Solution().trap(height2) << endl;
    // 1

    vector<int> height3 = {4, 2, 0, 3, 2, 5};
    cout << Solution().trap(height3) << endl;
    // 9

    return 0;
}

/// Source : https://leetcode.com/problems/trapping-rain-water/description/
/// Author : liuyubobobo
/// Time   : 2018-09-16

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int trap(vector<int>& height) {

        if(height.size() <= 2)
            return 0;

        vector<int> rdp(height.size(), -1);
        getR(0, height, rdp);

        vector<int> ldp(height.size(), -1);
        getL(height.size() - 1, height, ldp);

        int res = 0;
        for(int i = 0; i < height.size(); i ++)
            res += min(ldp[i], rdp[i]) - height[i];
        return res;
    }

private:
    int getR(int index, const vector<int>& height, vector<int>& rdp){

        if(index == height.size() - 1)
            return rdp[index] = height[index];

        return rdp[index] = max(height[index], getR(index + 1, height, rdp));
    }

    int getL(int index, const vector<int>& height, vector<int>& ldp){

        if(index == 0)
            return ldp[index] = height[index];

        return ldp[index] = max(height[index], getL(index - 1, height, ldp));
    }
};


int main() {

    vector<int> height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << Solution().trap(height1) << endl;
    // 6

    vector<int> height2 = {4,2,3};
    cout << Solution().trap(height2) << endl;
    // 1

    vector<int> height3 = {4, 2, 0, 3, 2, 5};
    cout << Solution().trap(height3) << endl;
    // 9

    return 0;
}

/// Source : https://leetcode.com/problems/trapping-rain-water/description/
/// Author : liuyubobobo
/// Time   : 2018-09-16

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int trap(vector<int>& height) {

        if(height.size() <= 2)
            return 0;

        vector<int> rdp(height.size(), height.back());
        for(int i = height.size() - 2; i >= 0; i --)
            rdp[i] = max(height[i], rdp[i + 1]);

        vector<int> ldp(height.size(), height[0]);
        for(int i = 1; i < height.size(); i ++)
            ldp[i] = max(height[i], ldp[i - 1]);

        int res = 0;
        for(int i = 0; i < height.size(); i ++)
            res += min(ldp[i], rdp[i]) - height[i];
        return res;
    }
};


int main() {

    vector<int> height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << Solution().trap(height1) << endl;
    // 6

    vector<int> height2 = {4,2,3};
    cout << Solution().trap(height2) << endl;
    // 1

    vector<int> height3 = {4, 2, 0, 3, 2, 5};
    cout << Solution().trap(height3) << endl;
    // 9

    return 0;
}

/// Source : https://leetcode.com/problems/trapping-rain-water/description/
/// Author : liuyubobobo
/// Time   : 2018-09-16

#include <iostream>
#include <vector>

using namespace std;


/// Using Stack
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int trap(vector<int>& height) {

        if(height.size() <= 2)
            return 0;

        vector<int> stack;
        int res = 0;
        for(int i = 0; i < height.size(); i ++){
            while(!stack.empty() && height[i] > height[stack.back()]){
                int cur = stack.back();
                stack.pop_back();
                if(stack.empty())
                    break;

                int dis = i - stack.back() - 1;
                int h = min(height[stack.back()], height[i]) - height[cur];
                res += h * dis;
            }
            stack.push_back(i);
        }
        return res;
    }
};


int main() {

    vector<int> height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << Solution().trap(height1) << endl;
    // 6

    vector<int> height2 = {4,2,3};
    cout << Solution().trap(height2) << endl;
    // 1

    vector<int> height3 = {4, 2, 0, 3, 2, 5};
    cout << Solution().trap(height3) << endl;
    // 9

    return 0;
}

/// Source : https://leetcode.com/problems/trapping-rain-water/description/
/// Author : liuyubobobo
/// Time   : 2018-09-16

#include <iostream>
#include <vector>

using namespace std;


/// Two Pointers
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int trap(vector<int>& height) {

        if(height.size() <= 2)
            return 0;

        int res = 0;
        int l = 0, r = height.size() - 1, lmax_i = l, rmax_i = r;
        while(l < r){
            if(height[l] < height[r]){
                l ++;
                if(height[l] < height[lmax_i])
                    res += min(height[lmax_i], height[rmax_i]) - height[l];
                else
                    lmax_i = l;
            }
            else{
                r --;
                if(height[r] < height[rmax_i])
                    res += min(height[lmax_i], height[rmax_i]) - height[r];
                else
                    rmax_i = r;
            }
        }
        return res;
    }
};


int main() {

    vector<int> height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << Solution().trap(height1) << endl;
    // 6

    vector<int> height2 = {4,2,3};
    cout << Solution().trap(height2) << endl;
    // 1

    vector<int> height3 = {4, 2, 0, 3, 2, 5};
    cout << Solution().trap(height3) << endl;
    // 9

    return 0;
}