Trapping Rain Water in C++ (Time Complexity: O(n))

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.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

Understanding the Problem

The core challenge of this problem is to determine how much water can be trapped between the bars of the elevation map after it rains. This problem is significant in various fields such as civil engineering for designing drainage systems and in computer graphics for simulating realistic water effects.

Potential pitfalls include misunderstanding how water is trapped between the bars and not accounting for all possible trapped water sections.

Approach

To solve this problem, we need to consider the height of the bars and how they form valleys where water can be trapped. Here are the steps to approach the solution:

Naive Solution

A naive solution would involve iterating through each bar and calculating the trapped water by finding the maximum height to the left and right of each bar. This approach, however, is not optimal as it has a time complexity of O(n^2).

Optimized Solution

We can optimize the solution using two main approaches:

1. Dynamic Programming

We can precompute the maximum height to the left and right of each bar and then use these precomputed values to calculate the trapped water in a single pass.

2. Two Pointers

We can use two pointers to traverse the elevation map from both ends towards the center, keeping track of the maximum heights seen so far from both directions. This approach has a time complexity of O(n) and a space complexity of O(1).

Algorithm

Let's break down the two-pointer approach step-by-step:

Initialize two pointers, left and right, at the beginning and end of the elevation map, respectively.
Initialize two variables, left_max and right_max, to keep track of the maximum heights seen so far from the left and right, respectively.
While the left pointer is less than the right pointer, do the following:
- If the height at the left pointer is less than or equal to the height at the right pointer:
  - If the height at the left pointer is greater than or equal to left_max, update left_max.
  - Otherwise, add the difference between left_max and the height at the left pointer to the total trapped water.
  - Move the left pointer one step to the right.
- Otherwise:
  - If the height at the right pointer is greater than or equal to right_max, update right_max.
  - Otherwise, add the difference between right_max and the height at the right pointer to the total trapped water.
  - Move the right pointer one step to the left.

Code Implementation

#include <vector>
#include <iostream>
using namespace std;

// Function to calculate the amount of trapped rain water
int trap(vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;

    int left = 0, right = n - 1;
    int left_max = 0, right_max = 0;
    int water_trapped = 0;

    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left]; // Update left_max
            } else {
                water_trapped += left_max - height[left]; // Calculate trapped water
            }
            left++; // Move left pointer to the right
        } else {
            if (height[right] >= right_max) {
                right_max = height[right]; // Update right_max
            } else {
                water_trapped += right_max - height[right]; // Calculate trapped water
            }
            right--; // Move right pointer to the left
        }
    }

    return water_trapped;
}

// Main function to test the trap function
int main() {
    vector<int> height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    vector<int> height2 = {4,2,0,3,2,5};

    cout << "Trapped water for height1: " << trap(height1) << endl; // Output: 6
    cout << "Trapped water for height2: " << trap(height2) << endl; // Output: 9

    return 0;
}

Complexity Analysis

The time complexity of the two-pointer approach is O(n) because we traverse the elevation map only once. The space complexity is O(1) as we use only a constant amount of extra space.

Edge Cases

Potential edge cases include:

All bars have the same height.
The elevation map is strictly increasing or decreasing.
The elevation map has only one bar.

Each of these cases should be tested to ensure the algorithm handles them correctly.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with small arrays.
Cases with large arrays to test performance.
Edge cases as mentioned above.

Using a testing framework like Google Test can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller parts and understand each part.
Think about different approaches and their trade-offs.
Practice solving similar problems to improve problem-solving skills.

Conclusion

Understanding and solving the Trapping Rain Water problem is crucial for developing strong problem-solving skills. By practicing and exploring different approaches, you can improve your ability to tackle similar problems efficiently.

Additional Resources

For further reading and practice, consider the following resources: