Trapping Rain Water in Java (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 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 units.

Approach

To solve this problem, we need to consider the height of the bars and how they form valleys where water can be trapped. A naive solution would involve checking each bar and calculating the trapped water by finding the maximum heights to the left and right of each bar. However, this approach is not optimal as it has a time complexity of O(n^2).

We can optimize this by using two pointers to traverse the elevation map from both ends towards the center. This approach ensures that we only pass through the elevation map once, achieving a time complexity of O(n).

Optimized Approach

1. Initialize two pointers, left and right, at the beginning and end of the elevation map, respectively.

2. Use two variables, leftMax and rightMax, to keep track of the maximum heights encountered from the left and right sides.

3. Move the pointers towards each other, updating the leftMax and rightMax values and calculating the trapped water based on the minimum of these two values.

Algorithm

1. Initialize left pointer to 0 and right pointer to n-1.

2. Initialize leftMax to height[0] and rightMax to height[n-1].

3. While left is less than right:

If height[left] is less than height[right], update leftMax and calculate trapped water at left pointer, then move left pointer to the right.
Otherwise, update rightMax and calculate trapped water at right pointer, then move right pointer to the left.

Code Implementation

public class TrappingRainWater {
    public int trap(int[] height) {
        // Edge case: if the array is empty or has less than 3 elements, no water can be trapped
        if (height == null || height.length < 3) {
            return 0;
        }

        int left = 0, right = height.length - 1;
        int leftMax = height[left], rightMax = height[right];
        int waterTrapped = 0;

        // Traverse the elevation map from both ends towards the center
        while (left < right) {
            if (height[left] < height[right]) {
                // Update leftMax and calculate trapped water at left pointer
                leftMax = Math.max(leftMax, height[left]);
                waterTrapped += leftMax - height[left];
                left++;
            } else {
                // Update rightMax and calculate trapped water at right pointer
                rightMax = Math.max(rightMax, height[right]);
                waterTrapped += rightMax - height[right];
                right--;
            }
        }

        return waterTrapped;
    }

    public static void main(String[] args) {
        TrappingRainWater solution = new TrappingRainWater();
        int[] height1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int[] height2 = {4, 2, 0, 3, 2, 5};
        System.out.println("Trapped water for height1: " + solution.trap(height1)); // Output: 6
        System.out.println("Trapped water for height2: " + solution.trap(height2)); // Output: 9
    }
}

Complexity Analysis

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

Edge Cases

Potential edge cases include:

Empty array or array with less than 3 elements: No water can be trapped.
All bars of the same height: No water can be trapped.
Bars with height 0: These should be handled correctly by the algorithm.

Testing these edge cases ensures the robustness of the solution.

Testing

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

Simple cases with small arrays.
Cases with varying heights and multiple valleys.
Edge cases as mentioned above.

Using a testing framework like JUnit can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem requirements and constraints thoroughly.
Break down the problem into smaller, manageable parts.
Consider both naive and optimized solutions, analyzing their trade-offs.
Practice solving similar problems to improve problem-solving skills.

Conclusion

Understanding and solving the Trapping Rain Water problem helps in developing a deeper understanding of array manipulation and two-pointer techniques. It is a common problem in technical interviews and has practical applications in various fields.

Practice and exploration of similar problems can further enhance problem-solving skills and algorithmic thinking.

Additional Resources

For further reading and practice, consider the following resources: