Trapping Rain Water Algorithm Solution

The trapping rain water problem asks us to calculate how much water can be trapped between bars of different heights. This classic algorithmic challenge demonstrates the application of two-pointer and dynamic programming techniques to solve optimization problems efficiently.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that the input array contains at least 3 elements, or should we handle edge cases like arrays with fewer than 3 elements?
2. Can the input array be mutated, or should we preserve the original input?
3. Are duplicate heights allowed in the input array?
4. What is the expected return format — just the total volume or also the individual water levels at each position?
5. What are the constraints on input size and element values (e.g., max array length, max height)?

Restate the pattern or problem type in your own words: The trapping rain water problem asks us to calculate how much water can be trapped between bars of different heights, given an elevation map represented as an array of non-negative integers. Each element represents the height of a bar, and water can be trapped between bars if there are taller bars on both sides.

Clarify the signal words and constraint shape that point to it: Signal words include "trapping," "water," "elevation map," "bars," and "volume." The constraint shape involves an array of heights where we're looking for a relationship between elements to determine trapped volume — specifically, the water level at each position depends on the maximum height to its left and right.

Note any assumptions you are making: I'm assuming that the input array contains at least 3 elements, as arrays with fewer than 3 elements cannot trap any water. I'm also assuming that the input array can be mutated if needed, but I'll implement a solution that preserves the original array.

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is best suited for static scenarios where the entire input array is available at once. It's not naturally suited for streaming or online processing because we need to know the maximum heights on both sides of each position, which requires a complete view of the array.

The problem is fundamentally about identifying local maxima and computing the difference between the minimum of left/right maxima and current height for each position.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Trapping rain water" or "volume of water that can be trapped"
• Arrays or lists of heights/levels
• "Bar chart" or "elevation map" visualization
• Input size typically up to 10⁵ elements (suggests O(n) or O(n log n) solutions)
• Constraints often include: heights are non-negative integers

Why this pattern fits better than alternatives: This is fundamentally a two-pointer or preprocessing problem that leverages the concept of "bounded" water levels. Unlike sliding window problems, it requires understanding how water is trapped between elevated boundaries. The key insight is that water at any position depends on the maximum heights to its left and right — making it a perfect fit for preprocessing or two-pointer techniques rather than brute force O(n²) checking.

Variations and related patterns:

• Container With Most Water: Similar two-pointer pattern but focused on maximizing area, not volume
• Stock Span Problem: Uses stack-based approach for finding "next greater element" — not applicable here
• Maximum Subarray: Uses Kadane's algorithm for contiguous sum, not trapping volume

Core insight: Water trapped at any position is determined by the minimum of the maximum heights to its left and right, minus the current height. This allows for efficient precomputation or two-pointer traversal to avoid redundant calculations.

The pattern is best suited for static input scenarios, where all data is available upfront and the problem can be solved in one pass or with preprocessing. It's not ideal for streaming data where new heights arrive over time.

3. Approach Evolution

Interview communication script:

My first instinct is to think about this as a brute force approach where for each position, I calculate how much water can be trapped by finding the maximum height to the left and right of that position. But that's O(n²) because for each position, I have to scan the entire array to find left and right maxima. Let me think about how to optimize this.

I notice that if I precompute the maximum heights from left and right for each position, I can reduce it to O(n) time. Actually, let me think about a two-pointer approach more carefully - if I maintain the invariant that the left pointer's max height is always less than or equal to the right pointer's max height, I can process from both ends toward the center.

The key insight is that for any position, the water level is determined by the minimum of the maximum heights to its left and right. But with two pointers, I can maintain that one side is always the limiting factor.

Brute-force approach and why it is not ideal:

The naive approach would be to iterate through each position and for each position, find the maximum height to its left and right. Then calculate trapped water as min(leftMax, rightMax) - height[i]. This results in O(n²) time complexity because for each position, we scan the entire array to find max left and right values.

Improved approach and the key optimization:

The key optimization is to precompute prefix and suffix maximum arrays. For each position, we can compute the maximum height from the left and from the right in O(n) time each. Then, for each position, we can calculate trapped water in O(1) time using the precomputed values.

Final approach with step-by-step reasoning:

I'll use a two-pointer technique that's more space-efficient than precomputation. I maintain two pointers at both ends of the array and track the maximum height seen so far from both directions. At each step, I move the pointer with smaller current height inward, because that position's water level is determined by that side's maximum height. This works because we're always guaranteed that the limiting factor (shorter wall) determines the water level at that position.

Important invariants that must hold:

1. Left pointer's max height is always less than or equal to right pointer's max height (this ensures we can safely calculate water levels from the left side)
2. The current water level at any position is bounded by min(leftMax, rightMax) - height[i]
3. We never process the same position twice, ensuring O(n) time complexity

4. Data Structure Choice

For the trapping rain water problem, I'll use a two-pointer approach with constant extra space, but let me analyze the key data structures:

Primary Data Structures:

1. Two pointers (left and right) - O(1) space, used to traverse the array from both ends
2. Integer variables - O(1) space, to track max heights from left and right sides

Why each data structure is needed:

• The two pointers maintain the invariant that we're always processing elements between our current left and right boundaries
• The max height variables track the maximum height encountered so far from each direction, which is crucial for calculating trapped water at any position

Time and space impact:

• Space complexity: O(1) - only using a constant amount of extra variables regardless of input size
• Time complexity: O(n) - single pass through the array with two pointers

Helper structures:

• No additional data structures needed beyond the two pointers and max height tracking variables
• The solution works in-place without requiring any auxiliary arrays or stacks

This approach is optimal because we don't need to store intermediate results or use additional memory for computation - the key insight is that we can calculate trapped water at each position using only the maximum heights seen so far from both directions.

5. Algorithm Walkthrough

Let me trace through the trapping rain water problem with a concrete example to demonstrate how our approach works.

Example: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Step-by-step execution:

1. Initialization:

   • left = 0, right = 11 (last index)
   • leftMax = 0, rightMax = 0
   • water = 0

2. First iteration (left = 0, right = 11):

   • height[left] = 0, height[right] = 1
   • Since height[left] < height[right], we process the left pointer
   • leftMax = max(0, 0) = 0
   • height[left] = 0 < leftMax = 0 → No water trapped (0 units)
   • Move left to 1

3. Second iteration (left = 1, right = 11):

   • height[left] = 1, height[right] = 1
   • Since height[left] <= height[right], we process the left pointer
   • leftMax = max(0, 1) = 1
   • height[left] = 1 == leftMax = 1 → No water trapped (0 units)
   • Move left to 2

4. Third iteration (left = 2, right = 11):

   • height[left] = 0, height[right] = 1
   • Since height[left] < height[right], we process the left pointer
   • leftMax = max(1, 0) = 1
   • height[left] = 0 < leftMax = 1 → Water trapped: leftMax - height[left] = 1 - 0 = 1 unit
   • water += 1
   • Move left to 3

5. Fourth iteration (left = 3, right = 11):

   • height[left] = 2, height[right] = 1
   • Since height[left] > height[right], we process the right pointer
   • rightMax = max(0, 1) = 1
   • height[right] = 1 == rightMax = 1 → No water trapped (0 units)
   • Move right to 10

6. Continue this process until left == right:

   • When left = 6, right = 6:
     • height[left] = 1, height[right] = 2
     • Since height[left] < height[right], process left pointer
     • leftMax = max(1, 1) = 1
     • height[left] = 1 == leftMax = 1 → No water trapped
     • Move left to 7

7. Final state:

   • When left = 7, right = 7:
     • height[left] = 3, height[right] = 2
     • Since height[left] > height[right], process right pointer
     • rightMax = max(1, 2) = 2
     • height[right] = 2 == rightMax = 2 → No water trapped
     • Move right to 6

8. Termination:

   • When left > right, we stop
   • Total water trapped = 6 units

Key observations:

• We always process the pointer with smaller height to ensure we're considering the limiting factor
• Water trapped at any position is determined by the difference between the max height on that side and current height
• The algorithm correctly handles all edge cases including flat surfaces, valleys, and peaks

The invariant maintained throughout is that at any point, the water trapped depends on the minimum of leftMax and rightMax, which ensures we never overcount or undercount trapped water.

6. Java Solution

public class TrappingRainWater {
    /**
     * Calculates the amount of water that can be trapped after raining.
     * Uses two pointers approach to achieve O(n) time and O(1) space complexity.
     * 
     * @param height Array of non-negative integers representing elevation map
     * @return Total units of trapped water
     */
    public int trap(int[] height) {
        // Handle edge cases
        if (height == null || height.length < 3) {
            return 0;
        }
        
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int trappedWater = 0;
        
        // Two pointers approach from both ends
        while (left < right) {
            // Move the pointer with smaller height
            if (height[left] < height[right]) {
                // If current height is greater than or equal to leftMax,
                // update leftMax (no water can be trapped here)
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    // Water trapped at current position
                    trappedWater += leftMax - height[left];
                }
                left++;
            } else {
                // If current height is greater than or equal to rightMax,
                // update rightMax (no water can be trapped here)
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    // Water trapped at current position
                    trappedWater += rightMax - height[right];
                }
                right--;
            }
        }
        
        return trappedWater;
    }
}

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the array to compute the leftMax array, another pass for the rightMax array, and a final pass to calculate the trapped water. Each of these passes is O(n), so the total time complexity is O(n).

Space Complexity: O(n)

The solution uses two auxiliary arrays: leftMax and rightMax, each of size n. Therefore, the space complexity is O(n). This is the primary trade-off in this approach - we trade space for time efficiency by precomputing the maximum heights.

Why These Bounds Are Correct:

The bounds are tight because:

1. We must examine each element at least once to determine the trapped water amount
2. The auxiliary arrays are necessary to avoid recomputing maximums repeatedly
3. No operations inside the loops have complexity worse than O(1)

Optimality:

This solution is optimal for the given constraints. While there exists an O(1) space two-pointer approach, this solution's O(n) time and space complexity is the best we can achieve for a static input array where we need to compute trapped water for all positions. The solution is near-optimal in both time and space complexity for the problem's requirements.

The approach avoids the O(n²) brute force where we'd compute max heights for each position in nested loops, making it significantly more efficient for large inputs.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle null or empty input gracefully to avoid ArrayIndexOutOfBoundsException
• Single element: No water can be trapped, return 0
• Two elements: No water can be trapped regardless of heights

Duplicate Values and Repeated States

• All same heights: Array like [3, 3, 3, 3] should return 0 water trapped
• Multiple peaks: Multiple local maxima can confuse naive approaches that only consider immediate neighbors

Boundary Conditions

• Zero heights: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] - zero heights at edges should not break the algorithm
• Consecutive equal heights: [1, 1, 1, 1] or [2, 2, 1, 1] - need to handle properly in the two-pointer approach

Common Implementation Mistakes

• Incorrect boundary handling: Forgetting to handle edge elements in the two-pointer approach, leading to off-by-one errors
• Wrong assumption about monotonicity: Assuming array is strictly increasing/decreasing when it's not
• Not maintaining proper invariants: In two-pointer approach, failing to maintain that leftMax and rightMax represent actual maximums seen so far
• Integer overflow: When summing large height values, though not an issue in typical constraints

Key Invariant Violations to Watch For

• Left pointer never exceeds right pointer: In two-pointer approach, ensure proper movement logic to avoid infinite loops
• Max tracking correctness: leftMax should always represent the maximum height seen from left, and similarly for rightMax
• Water calculation logic: Water trapped at index i is min(leftMax, rightMax) - height[i], not just the difference with one side

9. Alternative Approaches

There are several alternative approaches to solving the trapping rain water problem, each with different trade-offs:

1. Dynamic Programming Approach: Instead of using two pointers, we can precompute the maximum height to the left and right of every position. For each position, the water trapped is min(leftMax[i], rightMax[i]) - height[i]. This approach uses O(n) extra space but is intuitive and easy to understand.

2. Stack-based Approach: We can use a stack to keep track of indices where we might trap water. When we find a height greater than the height at the stack top, we can calculate trapped water between the current position and the stack top. This approach uses O(n) space in worst case and is more complex to implement correctly.

3. Brute Force Approach: For each position, find the maximum height on the left and right sides, then calculate trapped water as min(maxLeft, maxRight) - currentHeight. This is O(n²) time complexity and not suitable for large inputs.

4. Divide and Conquer: Split the array into halves recursively, but this approach is more complex to implement correctly and doesn't provide significant performance benefits over the two-pointer method.

The chosen two-pointer approach is preferred because it provides optimal O(n) time complexity with O(1) space complexity, making it the most efficient solution for this problem. The stack-based approach is more intuitive but has higher space complexity, while the brute force approach is too slow for practical use.

10. Test Cases

public class TrappingRainWater {
    public int trap(int[] height) {
        if (height == null || height.length < 3) return 0;
        
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }
        
        return water;
    }
}

Sample Test Cases

Example 1: Basic case

int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
// Expected: 6
// Water trapped at indices 2,4,5,6,9,10

Example 2: Edge case - empty array

int[] height = {};
// Expected: 0

Example 3: Edge case - minimal array

int[] height = {1, 0, 1};
// Expected: 1

Example 4: Monotonically increasing

int[] height = {1, 2, 3, 4, 5};
// Expected: 0
// No water can be trapped

Example 5: Monotonically decreasing

int[] height = {5, 4, 3, 2, 1};
// Expected: 0
// No water can be trapped

Example 6: Complex case with duplicates

int[] height = {3, 0, 2, 0, 4, 0, 2};
// Expected: 9
// Multiple trapped water regions

Example 7: Boundary case - all same height

int[] height = {2, 2, 2, 2};
// Expected: 0

Example 8: Single peak

int[] height = {2, 1, 3, 1, 2};
// Expected: 3
// Traps water between peaks at indices 0 and 2

11. Final Summary

The trapping rain water problem is elegantly solved using the two-pointer technique that maintains maximum heights from both ends, achieving optimal O(n) time and O(1) space complexity. The core insight is that for any position, the water level is determined by the minimum of the maximum heights to its left and right boundaries. By moving the pointer with the smaller boundary inward, we ensure we always have the correct local maximums to compute trapped water. This approach is both time and space optimal, making it the ideal solution for production systems where resource constraints matter. The algorithm's correctness stems from the invariant that at each step, we know the maximum height on one side and can compute the trapped water based on the smaller of the two boundaries, making it robust across all input configurations.