Trapping Rain Water: From Intuitive to Optimized Solutions - Top Tech & Investment Banking Interview Guide (Java, Hard, O(n))

• LeetCode 42 - Hard
• Companies(0-3 months): Goldman Sachs, Amazon, Google, TikTok, Bloomberg, Zopsmart, Meta, Microsoft, Snowflake, tsc

The Trapping Rain Water problem is a classic algorithmic challenge that tests your understanding of array manipulation and optimization techniques. Today, we'll explore two elegant solutions that showcase the evolution from a straightforward O(n) space approach to an optimal O(1) space solution.

Problem Overview

Given an array representing the height of bars, calculate how much rainwater can be trapped after it rains.

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Visualization:
    █
█   █ █   █
█ █ █ █ █ █ █
█ █ █ █ █ █ █ █
0 1 0 2 1 0 1 3 2 1 2 1

The Core Insight

The fundamental principle is:

For every position, the water it can trap equals min(maxLeft, maxRight) - height[i] (when positive).

This formula captures the essence of the problem - water at any position is constrained by the shortest wall on either side. Think of it as finding the "bottleneck" that determines the water level.

Solution Overview

We'll explore two approaches that both achieve O(n) time complexity:

1. Precomputation Approach (O(n) space): Use auxiliary arrays to store the maximum heights to the left and right of each position, then apply the formula in a final pass.

2. Two Pointers Approach (O(1) space): Use two pointers moving from both ends, maintaining running maximums and calculating water on-the-fly without extra space.

Solution 1: Precomputation Approach - O(n) Space

Our first solution takes a methodical approach by precomputing the maximum heights for every position.

public int trap(int[] height) {
    int n = height.length;
    if (n <= 2) return 0;

    // Arrays to store max heights to the left and right of each position
    int[] maxLeft = new int[n];
    int[] maxRight = new int[n];

    // Forward pass: compute maximum height to the left
    maxLeft[0] = height[0];
    for (int i = 1; i < n; i++) {
        maxLeft[i] = Math.max(maxLeft[i-1], height[i]);
    }

    // Backward pass: compute maximum height to the right
    maxRight[n-1] = height[n-1];
    for (int i = n-2; i >= 0; i--) {
        maxRight[i] = Math.max(maxRight[i+1], height[i]);
    }

    // Calculate trapped water using our core formula
    int totalWater = 0;
    for (int i = 0; i < n; i++) {
        int waterLevel = Math.min(maxLeft[i], maxRight[i]);
        if (waterLevel > height[i]) {
            totalWater += waterLevel - height[i];
        }
    }

    return totalWater;
}

Strategy Breakdown:

1. Forward Pass: Build maxLeft[] where maxLeft[i] represents the tallest bar from index 0 to i
2. Backward Pass: Build maxRight[] where maxRight[i] represents the tallest bar from index i to n-1
3. Water Calculation: Apply our formula at each position using the precomputed values

This approach is intuitive and easy to understand, making it perfect for initial problem-solving.

Solution 2: Two Pointers Optimization - O(1) Space ⭐

The elegant optimization comes from a key realization: we don't need to store all maximum values - we only need the current ones!

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int totalWater = 0;

    while (left < right) {
        // Process the side with the smaller height first
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];  // Update maximum, no water trapped
            } else {
                totalWater += leftMax - height[left];  // Trap water
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];  // Update maximum, no water trapped
            } else {
                totalWater += rightMax - height[right];  // Trap water
            }
            right--;
        }
    }

    return totalWater;
}

The Magic Behind Two Pointers

The brilliance of this approach lies in a subtle but powerful insight:

When height[left] < height[right], we know that:

• rightMax ≥ height[right] > height[left]
• Therefore, min(leftMax, rightMax) = leftMax
• We can safely calculate water at the left position using only leftMax

This eliminates the need for storing all maximum values while preserving the exact same logic!

When to Use Each Solution

Precomputation Approach:

• Great for learning and understanding the problem
• Easier to debug and trace through
• Good starting point in interviews

Two Pointers Approach:

• Optimal for production code
• Demonstrates advanced optimization skills
• Preferred solution for technical interviews

Key Takeaways

1. Pattern Recognition: This problem showcases the power of identifying the core mathematical relationship
2. Space Optimization: The evolution from O(n) to O(1) space demonstrates how clever insights can dramatically improve solutions
3. Two Pointers Technique: A versatile pattern that appears in many array problems

The Trapping Rain Water problem is more than just a coding challenge - it's a masterclass in algorithmic thinking and optimization. Start with the intuitive approach, understand the mechanics, then appreciate the elegance of the optimized solution.

What's your favorite approach? Have you encountered similar optimization patterns in other problems? Share your thoughts in the comments below!