MANG Problem #1: Trapping Rain Water (Hard)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

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.

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

2. The Mental Model: The "Bottleneck" Intuition

Imagine a single bar at index i. How much water can it hold? Water is trapped only if there is a higher "wall" on both its left and its right. The amount of water is determined by the shorter of those two walls, minus the height of the bar itself.

Formula: Water[i] = min(maxLeft, maxRight) - height[i]

3. Approach: Evolution from Brute to Staff-Tier

Stage 1: Brute Force ($O(N^2)$)

For every index, scan left to find the max, then scan right to find the max.

• Problem: Too many redundant scans. The interviewer will immediately ask for $O(N)$.

Stage 2: Dynamic Programming ($O(N)$ Time, $O(N)$ Space)

Pre-calculate leftMax[] and rightMax[] arrays in two passes.

• Problem: High memory overhead for large arrays.

Stage 3: Two Pointers ($O(N)$ Time, $O(1)$ Space)

Instead of pre-calculating everything, we use two pointers (left and right) and maintain leftMax and rightMax on the fly.

The Key Insight: If leftMax < rightMax, the water level at the left pointer is guaranteed to be limited by leftMax, regardless of what's in between. This is because we know there is a wall at least as tall as rightMax on the other side.

4. Visual Execution (Flowchart)

flowchart TD
    Start([Start]) --> Pointers[Initialize Left=0, Right=N-1]
    Pointers --> Loop{Left < Right?}
    Loop -- No --> End([End])
    Loop -- Yes --> Check{H[L] < H[R]?}
    Check -- Yes --> LMax{H[L] >= LMax?}
    Check -- No --> RMax{H[R] >= RMax?}
    LMax -- Yes --> SetLMax[Update LMax] --> IncL[Left++]
    LMax -- No --> AddL[Total += LMax - H[L]] --> IncL
    RMax -- Yes --> SetRMax[Update RMax] --> DecR[Right--]
    RMax -- No --> AddR[Total += RMax - H[R]] --> DecR
    IncL --> Loop
    DecR --> Loop

5. Detailed Dry Run Table

6. Java Implementation

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 totalWater = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                totalWater += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                totalWater += rightMax - height[right];
            }
            right--;
        }
    }
    return totalWater;
}

7. Verbal Interview Script (Staff Tier)

Interviewer: "Can you explain the intuition behind the two-pointer solution?"

You: "The fundamental constraint of the problem is that water at any point is limited by the minimum of the highest walls to its left and right. In the two-pointer approach, we leverage the fact that if the wall on the left (leftMax) is shorter than the wall on the right (height[right]), then the water level at the left pointer is strictly bounded by leftMax. We don't need to know the exact rightMax yet; we just need to know that a wall at least as tall as height[right] exists. This allows us to process the shorter side greedily, ensuring we only ever make a single pass over the data with constant space."

8. Common Pitfalls

1. The "min" mistake: Trying to use min(height[left], height[right]) instead of the running max variables.
2. Pointer overlap: Using while (left <= right). This can lead to double-counting the middle element.
3. Boundary logic: Not updating the max variables before adding the trapped water.

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'MANG Problem #1: Trapping Rain Water (Hard)', I focused on reducing the time complexity by leveraging a Two-Pointer strategy. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by using in-place modifications. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

1. Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
2. Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

• Problem: Too many redundant scans. The interviewer will immediately ask for $O(N)$.
• Problem: High memory overhead for large arrays.
• MANG Problem #2: Median of Two Sorted Arrays (Binary Search)

Read Next

• MANG Problem #2: Median of Two Sorted Arrays (Binary Search)
• Lesson: Monotonic Stacks and Area Optimization