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 algorithm question tests understanding of array manipulation, two-pointer techniques, and optimization strategies in coding interviews at FAANG companies.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input array be mutated, or should we preserve the original?
2. What are the constraints on array size and element values? (e.g., is it guaranteed to be non-negative?)
3. Should we return the total trapped water volume or just a single integer?
4. Are empty arrays or arrays with less than 3 elements valid inputs that we need to handle?
5. Do we need to consider overflow scenarios when computing the total volume?

Restatement in my own words: Given an array of non-negative integers representing vertical bars where each bar has width 1, determine how much water can be trapped between the bars after it rains. The water level at any position depends on the minimum of the maximum heights to its left and right.

Clarification of inputs, outputs, and constraints:

• Input: An array height of integers where height[i] represents the height of a bar at position i
• Output: A single integer representing the total volume of trapped water
• Constraints:
  • Array length can be up to 10⁵ (based on typical FAANG constraints)
  • Each element is non-negative integer
  • Water can only be trapped between bars, not above them

Assumptions I'm making:

• The array represents a 2D elevation map where each element is a vertical bar of unit width
• Water flows to the lowest point between two taller bars
• We're counting only water that gets trapped between bars, not water that would overflow

Data shape and hidden structure: The problem exhibits a "two-sided optimization" structure where for any position, the trapped water depends on both left and right boundaries. This suggests we're looking at a problem where we need to consider maximums from both directions, hinting toward a preprocessing or two-pointer approach.

The key insight is that for any position i, the water level above it equals min(max_height_left_of_i, max_height_right_of_i) - height[i], but only if this value is positive.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern here is Two Pointers or Dynamic Programming. This problem exhibits characteristics of a "bounded container" problem where we're trying to determine how much water can be trapped between bars of varying heights.

Wording that signals the pattern

The key phrases are:

• "Trapping rain water" - suggests we're looking for a bounded volume calculation
• "Between bars of different heights" - indicates we need to consider relative comparisons and boundaries
• The requirement to calculate "how much water" - implies we're computing a metric based on spatial relationships

Why this problem fits that pattern

This problem fits the Two Pointers pattern because:

1. We have a linear structure (array of heights)
2. The solution involves comparing elements from both ends toward the center
3. Each position's water capacity depends on the minimum of maximum heights from both sides
4. We can maintain invariants about left and right boundaries to avoid recomputation

Core insight needed to solve it

The core insight is that for any position i, the amount of water it can trap depends on:

• The maximum height to its left (leftMax)
• The maximum height to its right (rightMax)
• Water trapped at position i = min(leftMax, rightMax) - height[i]

This suggests we can process the array from both ends simultaneously, maintaining running maxima and computing water levels at each position.

The key optimization is that we don't need to precompute all left and right maxima separately - we can use a two-pointer approach that moves the pointer with the smaller current maximum, since that position is bounded by its own side's maximum height.

3. Approach Evolution

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 element, I need 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 by avoiding repeated scans. The key insight is that for any position, the water level above it is determined by the minimum of the maximum heights to its left and right, minus the current height.

Let me think about this more systematically. If I maintain running maximums from both directions, then for any position i, the water trapped at that position is min(maxLeft[i], maxRight[i]) - height[i]. This approach works because the water level is bounded by the shorter of the two boundaries, and we only care about what's trapped above the actual ground level.

The invariant I need to maintain is that at each position, I know what's the maximum height seen so far from both directions. This allows me to calculate the trapped water in a single pass.

The approach I'll use is two-pass with precomputed max arrays:

1. First pass: compute maxLeft array where maxLeft[i] = max height from 0 to i
2. Second pass: compute maxRight array where maxRight[i] = max height from i to end
3. Third pass: for each position, calculate trapped water as min(maxLeft[i], maxRight[i]) - height[i]

This is O(n) time and O(n) space, which is much better than the brute force O(n²) approach.

A more space-optimized approach would be using two pointers, but that's more complex to reason about and the O(n) solution is clean and readable. The two-pointer approach trades space for a more complex state management, but the time complexity remains O(n) in both cases.

The key optimization is recognizing that we don't need to recompute maxima at each position - they can be precomputed once and reused, which reduces the problem from nested iteration to linear passes.

4. Data Structure Choice

For the trapping rain water problem, I'll use a two-pointer approach with constant extra space, which is optimal for this problem.

Primary Data Structures Used

1. Two integer pointers (left, right) - These serve as our primary data structures to traverse the array from both ends toward the center. They maintain the invariant that we always know the maximum height seen so far from both directions.

2. Two integer variables (leftMax, rightMax) - These track the maximum height encountered from the left and right sides respectively as we move our pointers inward.

Why Each Data Structure Is Needed

The two pointers (left and right) are essential because they allow us to process the array in a single pass from both ends simultaneously. This is key to achieving O(n) time complexity without requiring additional space for precomputed arrays.

The leftMax and rightMax variables are crucial because they maintain the state we need to calculate trapped water at each position. At any given position, the amount of water that can be trapped depends on the minimum of the maximum heights to its left and right, minus the current height.

Time and Space Impact

• Time Complexity: O(n) - We traverse the array once with two pointers
• Space Complexity: O(1) - Only using a constant amount of extra space for the two pointers and two tracking variables

Helper Structure Consideration

I'm not using any helper data structures like stacks or arrays to precompute max values. This approach is more space-efficient than the O(n) auxiliary array solutions, and it's also more intuitive once you understand that we can maintain the necessary information with just two pointers.

This choice directly enables our optimal O(n) time and O(1) space solution, which is superior to the O(n) space solutions that would require precomputing left and right max arrays.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

Consider the input array: [0,1,0,2,1,0,1,3,2,1,2,1]

Step 1: Initialize variables

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

Step 2: First iteration

• height[left] = 0, height[right] = 1
• Since height[left] <= height[right]:
  • leftMax = max(0, 0) = 0
  • water += max(0, 0) - 0 = 0
  • Move left to 1

Step 3: Second iteration

• height[left] = 1, height[right] = 1
• Since height[left] <= height[right]:
  • leftMax = max(0, 1) = 1
  • water += max(1, 1) - 1 = 0
  • Move left to 2

Step 4: Third iteration

• height[left] = 0, height[right] = 1
• Since height[left] <= height[right]:
  • leftMax = max(1, 0) = 1
  • water += max(1, 1) - 0 = 1
  • Move left to 3

Step 5: Fourth iteration

• height[left] = 2, height[right] = 1
• Since height[left] > height[right]:
  • rightMax = max(0, 1) = 1
  • water += max(1, 1) - 1 = 0
  • Move right to 10

Step 6: Continue until convergence

• The process continues, with the key insight that we're always moving the pointer with the smaller height
• When height[left] <= height[right], we process from left side and update leftMax
• When height[left] > height[right], we process from right side and update rightMax
• The algorithm ensures that at each step, we know the maximum height on the opposite side

Edge case handling:

• When left == right, we stop (no more water can be trapped)
• The algorithm naturally handles arrays with all zeros or single elements
• For duplicate heights, the logic still works correctly due to the <= condition

The algorithm terminates when left >= right, ensuring we've processed all possible water-trapping positions.

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 totalWater = 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
                    totalWater += 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
                    totalWater += rightMax - height[right];
                }
                right--;
            }
        }
        
        return totalWater;
    }
}

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the input array with two pointers moving toward each other. Each element is visited at most twice - once by the left pointer and once by the right pointer, but since we're processing each position only once per pointer traversal, the total number of operations is linear in the input size.

Space Complexity: O(1)

The solution uses only a constant amount of extra space for variables left, right, maxLeft, maxRight, water, and loop counters. The space usage does not scale with input size, making it optimal for space complexity.

Why these bounds are correct:

The time complexity is linear because:

• We process each element exactly once in the context of our two-pointer approach
• The while loop condition left < right ensures each element is considered at most once per pointer movement
• Each iteration performs constant-time operations (comparisons, assignments, arithmetic)

The space complexity is constant because:

• We only maintain a fixed set of variables regardless of input size
• No recursive calls or dynamic data structures that grow with input
• The solution uses only primitive types and fixed-size variables

Optimality:

This solution achieves optimal time and space complexity for the trapping rain water problem. Since we must examine each element at least once to determine how much water can be trapped at that position, O(n) time complexity is unavoidable. The constant space usage is also optimal since we don't need to store any intermediate results or additional data structures that scale with input size.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle null or empty input gracefully to avoid NullPointerException or ArrayIndexOutOfBoundsException
• Single element: A single bar cannot trap any water, so return 0
• Two elements: Cannot trap water between two bars, return 0

Duplicate Values and Repeated States

• Duplicate heights: Multiple bars with same height can create confusion in boundary handling
• All same heights: All bars at same level results in zero trapped water but requires careful handling of the algorithm logic

Boundary Conditions

• First and last bars: These cannot trap water as they don't have bars on both sides
• Zero height bars: Bars with zero height should not contribute to trapped water calculation

Common Implementation Mistakes

• Incorrect boundary handling: Forgetting that first and last elements cannot trap water
• Off-by-one errors: Mismanaging indices when computing left/right max arrays or sliding window
• Wrong max tracking: Not properly maintaining running maximums when iterating from left to right or right to left
• Integer overflow: When computing total trapped water, ensure intermediate calculations don't overflow (though not an issue with typical constraints)
• Inconsistent state management: Not properly maintaining the invariant that we're always looking at the maximum height seen so far

Example of a Common Pitfall

// Incorrect: Not handling edge cases properly
int[] height = {3, 0, 0, 2, 0, 4};
// If we don't handle the case where first/last elements can't trap water,
// our algorithm might incorrectly calculate trapped water for those positions

The key is to always validate input bounds and ensure that our algorithm correctly identifies which bars can actually trap water (those that are bounded by higher bars on both sides).

9. Alternative Approaches

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

Brute Force Approach: For each position, calculate the maximum height to its left and right, then take the minimum of these two values minus the current height. This approach has O(n²) time complexity as we need to scan left and right for each position. While simple to understand, it's inefficient for large inputs.

Dynamic Programming: Precompute the maximum height from left and right for each position in two passes, then calculate trapped water at each position. This reduces time complexity to O(n) but requires O(n) extra space for the precomputed arrays. This is more efficient than brute force but uses additional memory.

Two Pointers Approach: Use two pointers starting from both ends, maintaining the maximum height seen so far from both sides. Move the pointer with smaller current height inward, as that side determines the water level. This approach achieves O(n) time complexity with O(1) space complexity, making it optimal in both time and space.

Stack-Based Approach: Use a stack to keep track of indices where we might form water traps. When we find a height greater than the stack top, we can calculate trapped water between the current element and the previous elements in the stack. This approach also runs in O(n) time but uses O(n) space in worst case, similar to the dynamic programming approach.

The stack-based approach is particularly elegant for problems involving "water trapping" or "container with most water" patterns, but the two-pointer approach is generally preferred for this specific problem due to its optimal space complexity and clean implementation.

The two-pointer approach is the most practical alternative since it matches our chosen solution in time complexity while offering better space efficiency, making it ideal for systems with memory constraints.

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 result = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    result += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    result += rightMax - height[right];
                }
                right--;
            }
        }
        
        return result;
    }
}

Sample Test Cases

// Test case 1: Basic example from problem description
int[] height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
// Expected: 6
// Water trapped at indices 2,4,5,6,9,10

// Test case 2: Empty array
int[] height2 = {};
// Expected: 0

// Test case 3: Single element
int[] height3 = {1};
// Expected: 0

// Test case 4: Two elements
int[] height4 = {1, 2};
// Expected: 0

// Test case 5: All same height
int[] height5 = {2, 2, 2, 2};
// Expected: 0

// Test case 6: Strictly increasing
int[] height6 = {1, 2, 3, 4, 5};
// Expected: 0

// Test case 7: Strictly decreasing
int[] height7 = {5, 4, 3, 2, 1};
// Expected: 0

// Test case 8: Peak at beginning
int[] height8 = {5, 1, 2, 3, 4};
// Expected: 3

// Test case 9: Peak at end
int[] height9 = {1, 2, 3, 4, 5};
// Expected: 0

// Test case 10: Complex case with multiple peaks
int[] height10 = {3, 0, 2, 0, 4, 1, 3};
// Expected: 8

Tricky Edge Cases

// Test case 11: Large values causing overflow in naive approaches
int[] height11 = {1000000, 0, 1000000};
// Expected: 1000000

// Test case 12: Duplicate heights
int[] height12 = {2, 0, 2, 0, 2};
// Expected: 4

// Test case 13: Large array size (boundary test)
int[] height13 = new int[100000];
Arrays.fill(height13, 1);
// Expected: 0 (all same height)

Boundary Conditions

// Test case 14: Minimum valid input size (3 elements)
int[] height14 = {1, 0, 1};
// Expected: 1

// Test case 15: Maximum height constraint (typically 10^6)
int[] height15 = {1000000, 0, 1000000};
// Expected: 1000000

The test cases cover all major scenarios including edge cases like empty arrays, minimal inputs, uniform heights, monotonic sequences, and complex configurations with multiple peaks. These tests validate both correctness and robustness of the solution across various input conditions.

11. Final Summary

The core insight is that water trapped at any position depends on the minimum of maximum heights to its left and right boundaries. This problem is elegantly solved using the two-pointer technique that maintains invariants about left and right maximums, achieving optimal O(n) time and O(1) space complexity. The solution works by greedily processing the smaller height boundary at each step, ensuring we never overcount trapped water while maintaining correctness through careful invariant maintenance. This approach is both intuitive and highly efficient, making it the preferred solution for production systems requiring optimal resource utilization.