Trapping Rain Water

Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season.

• Time : O(n)
• Space : O(1)

class Solution {

    // Function to find the trapped water between the blocks.
public:
    long long trappingWater(int arr[], int n) {
        vector<pair<int, int>> st;
        long long res = 0, l = 0, r = n - 1, mi = 0;
        while(l < r) {
            if(arr[l] < arr[r]) {
                if(arr[l] <= mi) res -= arr[l++];
                else {
                    res -= mi;
                    res += (r - l - 1) * (arr[l] - mi);
                    mi = arr[l++];
                }
            } else {
                if(arr[r] <= mi) res -= arr[r--];
                else {
                    res -= mi;
                    res += (r - l - 1) * (arr[r] - mi);
                    mi = arr[r--];
                }
            }
        }
        return res;
    }
};

• if problem asks maximum pool of water
• Time : O(n)
• Space : O(1)

class Solution {

    // Function to find the trapped water between the blocks.
public:
    long long trappingWater(int arr[], int n) {
        vector<pair<int, int>> st;
        long long res = 0, l = 0, r = n - 1;
        
        for(int i = 0, minus = 0; i < n; i++) {
            if(arr[i] == 0) continue;
            if(st.empty()) st.push_back({0, i});
            else if(arr[st.back().second] >= arr[i]) {
                res = max(res, 1ll * (i - st.back().second - 1) * min(arr[st.back().second], arr[i]));
                st.push_back({0, i});
            } else {
                int block = 0;
                while(!st.empty() and arr[st.back().second] < arr[i]) {
                    res = max(res, 1ll * (i - st.back().second - 1) * min(arr[st.back().second], arr[i]) - block);
                    block += arr[st.back().second] + st.back().first;
                }
                if(!st.empty()) {
                    res = max(res, 1ll * (i - st.back().second - 1) * min(arr[st.back().second], arr[i]) - block);
                }
                st.push_back({block, i});
            }
        }
        return res;
    }
};