Trapping Rain Water In C++

Introduction:

In C++, solving the challenge of capturing rainwater is a well-known issue that revolves around effectively computing the volume of water that can be held within the bars of a specified terrain denoted by an array. The objective is to determine the total quantity of accumulated water. The resolution commonly involves the application of either two-pointer or dynamic programming methodologies. Begin by traversing the array to pinpoint potential locations where water can be trapped, and employ left and right pointers to monitor the tallest bars encountered from both directions. Subsequently, determine the water level at each location by considering the minimum height of the neighboring bars. Aggregate these water levels together to derive the ultimate outcome.

Program:

#include <iostream>
#include <vector>
using namespace std;
int trap(vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;
    vector<int> leftMax(n, 0), rightMax(n, 0);
    leftMax[0] = height[0];
    for (int i = 1; i < n; ++i) {
        leftMax[i] = max(leftMax[i - 1], height[i]);
    }
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        rightMax[i] = max(rightMax[i + 1], height[i]);
    }
    int trappedWater = 0;
    for (int i = 0; i < n; ++i) {
        trappedWater += min(leftMax[i], rightMax[i]) - height[i];
    }
    return trappedWater;
}
int main() {
    // Example usage
    vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1};
    int result = trap(heights);
    cout << "Trapped Water: " << result << endl;
    return 0;
}

Output:

Trapped Water: 6

Explanation:

At the beginning of the process, we set up the initial values and establish the base case.

The process commences with verifying whether the dimension of the input array height is less than or equal to 2. In such a case, it will output 0, indicating insufficient bars for water trapping. Next, the initial step involves preparing the Maximum Heights for both the Left and Right.

Two extra arrays, known as leftMax and rightMax, are established to hold the maximum height observed from the left and right sides, correspondingly.

The leftMax array gets populated by traversing the input array in a left-to-right manner, constantly updating the highest height seen at each index.

Likewise, the rightMax array gets populated by looping from the right side towards the left.

• ✅ Determining Trapped Water:

Following this, a loop goes through every index within the input array.

For every index, the algorithm computes the volume of trapped water by determining the lowest elevation among the highest points on the left (leftMax) and right (rightMax) sides, then deducting the height of the current column.

The outcome is the total of the accumulated water levels at each location.

• ✅ Result and Output:

The ultimate outcome, indicating the complete amount of water captured, is displayed or can be utilized for additional purposes if required.

Complexity analysis:

Time Complexity:

The time complexity of the code is O(n), with n representing the size of the input array height.

The loop goes over the array thrice: first to compute the left side, then for the rightMax, and finally to calculate the trapped water. Every cycle requires a linear search of the array.

Space Complexity:

The space complexity is O(n) .

Extra memory is allocated for two arrays (leftMax and rightMax), both with a length of n, to save the highest heights from the left and right sides at each index.

The memory allocated for these arrays increases in direct proportion to the size of the input array.

Approach 1: Using Two-Pointer

Implement a solution with a pair of pointers, where one pointer initiates from the start and the other from the end of the array. Progressively, adjust these pointers inward while retaining the highest height encountered from both the left and right sides.

Program:

#include <iostream>
#include <vector>
using namespace std;
int trap(vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;
    int left = 0, right = n - 1;
    int leftMax = 0, rightMax = 0;
    int trappedWater = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            // Update leftMax and calculate trapped water at lefcpp tutorialer
            leftMax = max(leftMax, height[left]);
            trappedWater += max(0, leftMax - height[left]);
            left++;
        } else {
            // Update rightMax and calculate trapped water at righcpp tutorialer
            rightMax = max(rightMax, height[right]);
            trappedWater += max(0, rightMax - height[right]);
            right--;
        }
    }
    return trappedWater;
}
int main() {
    // Example usage
    vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1};
    int result = trap(heights);
    cout << "Trapped Water: " << result << endl;
    return 0;
}

Output:

Trapped Water: 6

Explanation:

• ✅ Initialization:

Two pointers, denoted as left and right, are set at the start and end of the given array named height.

Two variables, leftMax and rightMax, are set to store the maximum heights observed from the left and right sides correspondingly.

Another variable, named trappedWater, is set up to monitor the cumulative trapped water.

• ✅ Primary Iteration:

The primary iteration continues executing while the left pointer is smaller than the right pointer in the C++ tutorial, guaranteeing their gradual convergence.

• ✅ During each cycle:

If the height on the left side of the tutorial is lower than the height on the right side of the tutorial:

Update the variable leftMax by assigning it the greater value between its current state and the height at the left side.

Calculate and include the trapped water within the container by determining the variance between the leftMax and the current height at the specific location.

Move the lefcpp tutorialer to the right.

If the height at the leftcpp tutorialer is greater than or equal to the height at the rightcpp tutorialer (or if they are equal)

Update the rightMax variable by choosing the higher value between its current value and the height located at the right side.

Calculate and incorporate the volume of water trapped at the right angle triangle by considering the disparity between the correct mixture and the height at the right angle triangle.

Result: Move the cpp tutorial to the left.

The end outcome is the total trappedWater once the loop finishes iterating.

Complexity analysis:

Time Complexity:

The time complexity is O(n), with n representing the length of the input array height.

The algorithm iterates once through the array, adjusting either the left or right pointer towards the center during each iteration. The process continues until the pointers converge.

Space Complexity:

The space complexity is O(1), denoting consistent utilization of memory.

The algorithm employs a set quantity of variables (left, right, leftMax, rightMax, trappedWater) irrespective of the array's size. It does not necessitate extra space corresponding to the input size.

Approach 2: Using Stack

Utilize a stack to maintain a record of the indexes of the bars. The stack should hold the indexes of the bars in ascending order based on their heights.

Loop through the array of heights, and for each column, calculate the volume of water it can trap.

If the height of the current bar exceeds the height of the top bar in the stack, remove elements from the stack and compute the volume of trapped water until a bar with a height that is equal to or higher is reached.

Program:

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int trap(vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;
    int trappedWater = 0;
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int topIdx = st.top();
            st.pop();
            if (st.empty()) break;
            int distance = i - st.top() - 1;
            int boundedHeight = min(height[i], height[st.top()]) - height[topIdx];
            trappedWater += distance * boundedHeight;
        }
        st.push(i);
    }
    return trappedWater;
}
int main() {
    // Example usage
    vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1};
    int result = trap(heights);
    cout << "Trapped Water: " << result << endl;
    return 0;
}

Output:

Trapped Water: 6

Explanation:

• ✅ Initialization:

We begin by setting up two variables: trappedWater to monitor the accumulated trapped water and a stack st to hold the indexes of the bars.

• ✅ Primary Iteration:

We loop over the array of heights, handling each bar individually as we go through them.

For every bar, we verify whether the stack is vacant or if the height of the current bar is lower or equal to the height of the top bar in the stack.

If the condition is true, we add the index of the current bar to the stack.

If false, it signifies that the height of the current bar exceeds the height of the bar at the stack's top, suggesting a possible location where water may accumulate.

We initiate a loop in which we remove elements from the stack until the stack becomes empty or the height of the current bar exceeds the height of the bar at the stack's top.

During the process of removing elements from the stack, we determine the amount of water trapped between each removed bar and adjust the total trapped water value accordingly.

The amount of water trapped above each removed bar is determined by multiplying the distance between the current bar and the highest bar in the stack by the disparity in heights between the current bar and the removed bar, taking into account the lesser of the two heights.

• ✅ Finishing and Outcome:

Once all bars have been processed, the loop comes to an end.

We provide the resulting trappedWater value, indicating the overall amount of water trapped in the terrain.

Complexity analysis:

Time Complexity:

The time complexity is O(n), with 'n' representing the quantity of bars present in the height input array.

Each individual bar undergoes processing just once at most in the worst-case scenario. During each cycle, tasks such as adding to or removing elements from the stack are executed in constant time.

Space Complexity:

The spatial complexity is O(n), with 'n' representing the quantity of bars in the height input array.

The stack is capable of holding all the bars at most in the worst-case scenario. Furthermore, the remaining variables (trappedWater, loop index) necessitate a constant amount of space.

The total amount of space required increases in a linear manner based on the quantity of bars present in the input array.

Approach 3: Using Dynamic Programming

Calculate in advance the tallest height possible on the left and right sides for every bar and store these values in two distinct arrays.

Determine the amount of water trapped at every bar by comparing the lower of the two highest bars on the left and right sides.

Program:

#include <iostream>
#include <vector>
using namespace std;
int trap(vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;
    // Initialize leftMax and rightMax arrays
    vector<int> leftMax(n, 0);
    vector<int> rightMax(n, 0);
    // Compute maximum heights from the left
    leftMax[0] = height[0];
    for (int i = 1; i < n; ++i) {
        leftMax[i] = max(leftMax[i - 1], height[i]);
    }
    // Compute maximum heights from the right
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        rightMax[i] = max(rightMax[i + 1], height[i]);
    }
    // Calculate trapped water
    int trappedWater = 0;
    for (int i = 0; i < n; ++i) {
        trappedWater += min(leftMax[i], rightMax[i]) - height[i];
    }
    return trappedWater;
}
int main() {
    // Example usage
    vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1};
    int result = trap(heights);
    cout << "Trapped Water: " << result << endl;
    return 0;
}

Output:

Trapped Water: 6

Explanation:

• ✅ Initialization:

We begin by setting up two arrays, leftMax and rightMax, to hold the maximum heights found from the left and right side of each bar, correspondingly.

The dimensions of these arrays match the height of the input array.

• ✅ Calculating Maximum Heights in Advance:

We populate the leftMax array by traversing the height input array from the left-hand side to the right-hand side.

For every individual bar, we refresh the leftMax value at that specific position by comparing its existing value with the height of the current bar and choosing the larger value.

This procedure guarantees that leftMax[i] holds the highest encountered height from the left side for the bar located at index i.

Likewise, the rightMax array is populated by traversing the height array input from the right side to the left side.

For every individual bar, we modify the rightMax value at that specific location by selecting the higher value between its existing value and the height of the current bar.

This procedure guarantees that the value in rightMax[i] represents the highest height encountered to the right of the bar located at index i.

When it comes to computing Trapped Water:

After determining the tallest points on the left and right edges, we proceed to cycle through the given height array.

For every bar located at index i, we compute the amount of water trapped at that specific location:

We calculate the lesser value between leftMax[i] and rightMax[i], which signifies the minimum of the highest heights from the left and right limits for the current bar.

We deduct the current bar height[i] from the minimum value to determine the amount of water trapped at that specific position.

This measurement signifies the volume of water that can be contained within the present bar.

We collect this confined water from each bar to calculate the overall trapped water volume.

Returning the Result:

Finally, we retrieve the overall volume of trapped water that was calculated in the preceding stage.

Complexity analysis:

Time Complexity:

The time complexity is O(n), with n representing the quantity of bars in the height input array.

Two iterations are performed on the input array: the first to calculate the maximum heights from the left side, and the second to determine the maximum heights from the right side.

In addition, a singular iteration through the input array is performed to compute the amount of trapped water for each bar.

In general, the time complexity stays linear in relation to the quantity of bars in the input array.

Space Complexity:

The space complexity is O(n), with n representing the quantity of bars in the given array height.

Extra memory is allocated for two arrays (leftMax and rightMax), both with a length of n, to hold the highest heights from the left and right edges for every bar.

The amount of memory used increases in relation to the size of the input array, yet it remains constant regardless of the input array's size.

The total space complexity continues to scale linearly in correlation with the quantity of bars present in the input array.