How to Solve Trapping Rain Water

Start by precomputing the maximum height to the left and right of each bar, then calculate trapped water at each index. Using a two-pointer or stack approach reduces unnecessary iterations while handling edge cases where heights vary irregularly. This approach ensures accurate accumulation without missing dips or overcounting peaks, effectively translating state transitions into trapped water calculations.

Problem Statement

You are given an array of non-negative integers representing an elevation map where the width of each bar is 1. The goal is to compute how much rain water can be trapped after raining. Each element in the array represents the height of a vertical bar, and water can only be trapped between higher bars. The challenge is to calculate the total units of trapped water efficiently using patterns like dynamic programming, two pointers, or stacks.

For example, consider an elevation map given by height = [0,1,0,2,1,0,1,3,2,1,2,1]. Water accumulates in valleys formed between bars, and the total trapped water for this input is 6 units. Constraints include arrays with length up to 20,000 and heights up to 100,000, making naive iteration inefficient. Correct handling of peaks, valleys, and plateaus is essential for accurate computation.

Examples

Example 1

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

Output: 6

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

Example details omitted.

Constraints

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Solution Approach

Dynamic Programming with Precomputed Max Arrays

Compute two auxiliary arrays: left_max[i] storing the maximum height to the left of i, and right_max[i] storing the maximum height to the right. Then, iterate through the array and calculate trapped water at each index as min(left_max[i], right_max[i]) - height[i]. This method leverages the state transition dynamic programming pattern to avoid redundant calculations and guarantees O(n) time, though it uses O(n) extra space for the auxiliary arrays.

Two-Pointer Approach

Use two pointers starting at both ends of the elevation map, maintaining left_max and right_max variables. Move the pointer with the smaller height inward, updating max heights and accumulating water based on min(left_max, right_max) - height[i]. This method reduces space complexity to O(1) while still ensuring O(n) time. It directly handles valleys and peaks dynamically, reflecting the core state transition pattern of trapped water computation.

Monotonic Stack Approach

Iterate through the height array while maintaining a stack of indices in decreasing order. When the current height exceeds the stack top, pop the stack and calculate water trapped using the distance and bounded height. This approach effectively identifies local valleys and leverages the stack to model state transitions between peaks, achieving O(n) time with O(n) space. It handles irregular dips efficiently and prevents double-counting water units.

Complexity Analysis

The solution can achieve O(n) time by visiting each bar once using dynamic programming, two-pointer, or stack approaches. Space complexity varies: O(n) for precomputed max arrays or stack, and O(1) for the optimized two-pointer approach. These complexities ensure scalable performance for input sizes up to 20,000 elements without unnecessary overhead.

What Interviewers Usually Probe

• Do you understand why precomputing left and right max heights ensures correct trapped water calculation?
• Can you explain how two-pointer traversal reduces space usage while maintaining accurate state transitions?
• Will you handle edge cases where consecutive bars are equal or the array has a single peak?

Common Pitfalls or Variants

Common pitfalls

• Failing to update left_max or right_max properly, causing underestimation of trapped water in valleys.
• Confusing index distances when using the stack approach, leading to overcounting trapped units.
• Assuming all dips trap water without considering the bounding higher bars, which results in incorrect totals.

Follow-up variants

• Compute trapped water when elevation map elements are floating-point heights instead of integers.
• Calculate trapped water using only constant extra space without modifying the original array.
• Determine the maximum single valley water accumulation instead of total trapped water.

How GhostInterview Helps

• Capture the input array visually or through screenshots to verify each step and ensure consistent evaluation.
• Provide the solution path, including dynamic programming state transitions and two-pointer decisions, along with time and space complexity explanations.
• Support real-time screen-sharing workflows and capture intermediate layers, highlighting water accumulation at each index for clarity.

Topic Pages

• Array
• Two Pointers
• Dynamic Programming
• Stack
• Monotonic Stack

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

How does the dynamic programming pattern apply to Trapping Rain Water?

Dynamic programming stores maximum heights to the left and right of each bar to calculate trapped water efficiently, avoiding repeated scans for each index.

Can I solve this problem with constant space?

Yes, the two-pointer approach maintains left_max and right_max variables only, achieving O(1) space while still computing trapped water correctly.

Why does the monotonic stack method work for this problem?

The stack identifies previous peaks and local valleys, modeling state transitions between bars and ensuring each trapped unit is counted precisely once.

What edge cases should I watch for in Trapping Rain Water?

Watch arrays with all equal heights, strictly increasing or decreasing heights, and single or multiple peaks that can cause zero or partial water trapping.

How do I calculate trapped water for irregular valleys?

Use precomputed left and right max or a stack to dynamically assess the bounding heights, ensuring even uneven dips are measured correctly for trapped water.