Trapping Rain Water Problem in DSA Java

Mental Model

We want to find how much water can be trapped between bars of different heights after it rains.

Analogy: Imagine a row of buildings with different heights. Rainwater collects in the dips between taller buildings, like water filling valleys between hills.

Height bars: 3 0 2 0 4
Visual: 4 |       ↑
        3 | ↑     ↑
        2 | ↑   ↑ ↑
        1 | ↑   ↑ ↑
        0 | ↑ ↑ ↑ ↑ ↑
          ----------------
          0 1 2 3 4 (indices)

Dry Run Walkthrough

Input: height array: [3, 0, 2, 0, 4]

Goal: Calculate total trapped rainwater between the bars

Step 1: Find max height to the left of each bar

leftMax = [3, 3, 3, 3, 4]

Why: We need the tallest bar on the left to know how much water can be held

Step 2: Find max height to the right of each bar

rightMax = [4, 4, 4, 4, 4]

Why: We need the tallest bar on the right to know the water limit

Step 3: Calculate trapped water at each bar as min(leftMax, rightMax) - height

water = [0, 3, 1, 3, 0]

Why: Water trapped depends on the smaller boundary minus current height

Step 4: Sum all trapped water amounts

total water = 0 + 3 + 1 + 3 + 0 = 7

Why: Total trapped water is sum of water above each bar

Result:

Final trapped water: 7 units

Annotated Code

DSA Java

public class TrappingRainWater {
    public static int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]); // build left max array
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]); // build right max array
        }

        int trappedWater = 0;
        for (int i = 0; i < n; i++) {
            trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i]; // sum trapped water
        }

        return trappedWater;
    }

    public static void main(String[] args) {
        int[] height = {3, 0, 2, 0, 4};
        int result = trap(height);
        System.out.println("Trapped water: " + result);
    }
}

leftMax[i] = Math.max(leftMax[i - 1], height[i]); // build left max array

build array of tallest bar from left up to current index

rightMax[i] = Math.max(rightMax[i + 1], height[i]); // build right max array

build array of tallest bar from right up to current index

trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i]; // sum trapped water

calculate water trapped on current bar and add to total

Output

Trapped water: 7

Complexity Analysis

Time: O(n) because we scan the height array three times linearly

Space: O(n) because we use two extra arrays to store left and right max heights

vs Alternative: Compared to a naive O(n^2) approach checking max heights for each bar repeatedly, this is much faster

Edge Cases

empty height array

returns 0 as no bars means no trapped water

DSA Java

if (n == 0) return 0;

all bars same height

returns 0 because no dips to trap water

DSA Java

trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i];

strictly increasing or decreasing bars

returns 0 because water cannot be trapped on slopes

DSA Java

trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i];

When to Use This Pattern

When you see a problem asking how much water can be trapped between bars or heights, use the trapping rain water pattern with left and right max arrays to find boundaries efficiently.

Common Mistakes

Mistake: Forgetting to handle empty input array causing errors
Fix: Add a guard clause to return 0 if input length is zero

Mistake: Using max height from only one side leading to incorrect trapped water calculation
Fix: Calculate max heights from both left and right sides before summing trapped water

Mistake: Subtracting height from max height without taking minimum of left and right max
Fix: Use min(leftMax[i], rightMax[i]) to find correct water level at each bar

Summary

Calculates total water trapped between bars of different heights after rain.

Use when you need to find how much water can be held between vertical bars or walls.

The key insight is water trapped depends on the smaller tallest bar on either side minus the current bar height.

Practice

1. What does the Trapping Rain Water problem ask you to find given an array of heights?

easy

A. The total amount of water that can be trapped between the bars after raining

B. The maximum height of the bars in the array

C. The minimum height of the bars in the array

D. The number of bars that are taller than their neighbors

Solution

1. Step 1: Understand the problem statement

   The problem asks to calculate how much water can be trapped between bars of different heights after it rains.

2. Step 2: Identify the goal

   The goal is to find the total volume of trapped water, not just heights or counts of bars.

3. Final Answer:

   The total amount of water that can be trapped between the bars after raining -> Option A

4. Quick Check:

   Trapping rain water = total trapped water volume [OK]

Hint: Focus on trapped water volume, not bar heights [OK]

Common Mistakes:

• Confusing trapped water with max bar height
• Counting bars taller than neighbors instead of water
• Calculating minimum height instead of trapped water

2. Which of the following Java code snippets correctly initializes an array of heights for the Trapping Rain Water problem?

easy

A. int[] heights = new int(6) {4, 2, 0, 3, 2, 5};

B. int heights = [4, 2, 0, 3, 2, 5];

C. int[] heights = (4, 2, 0, 3, 2, 5);

D. int[] heights = {4, 2, 0, 3, 2, 5};

Solution

1. Step 1: Check Java array initialization syntax

   In Java, arrays are initialized with curly braces {} and type declaration like int[].

2. Step 2: Validate each option

   int[] heights = {4, 2, 0, 3, 2, 5}; uses correct syntax: int[] heights = {4, 2, 0, 3, 2, 5}; Options B, C, and D use invalid syntax.

3. Final Answer:

   int[] heights = {4, 2, 0, 3, 2, 5}; -> Option D

4. Quick Check:

   Java array init uses {} with type[] [OK]

Hint: Use curly braces {} with type[] to initialize arrays [OK]

Common Mistakes:

• Using square brackets [] without type[]
• Using parentheses () instead of braces {}
• Trying to initialize array with new int(size) and values together

3. What is the output of the following Java code snippet for trapping rain water?

int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(trap(height));

public static int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, 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;
}

medium

A. 5

B. 6

C. 7

D. 8

Solution

1. Step 1: Understand two-pointer approach

   We use two pointers left and right, track max heights on both sides, and add trapped water where possible.

2. Step 2: Trace the code with given input

   For input {0,1,0,2,1,0,1,3,2,1,2,1}, the trapped water calculated is 6 units.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Two-pointer trap calculation = 6 [OK]

Hint: Use two pointers and track max heights from both ends [OK]

Common Mistakes:

• Not updating leftMax and rightMax correctly
• Adding negative water amounts
• Confusing left and right pointer movements

4. Identify the bug in this Java method for trapping rain water:

public static int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, 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;
}

medium

A. The water calculation should add height[left] instead of subtracting

B. The comparison should be 'height[left] <= height[right]' instead of '<'

C. The loop condition should be 'left < right' instead of 'left <= right'

D. leftMax and rightMax should be initialized to 1 instead of 0

Solution

1. Step 1: Analyze loop condition impact

   The loop uses 'left <= right', which causes double counting when left == right.

2. Step 2: Correct loop condition

   Changing to 'left < right' prevents overlapping pointers and avoids incorrect water calculation.

3. Final Answer:

   The loop condition should be 'left < right' instead of 'left <= right' -> Option C

4. Quick Check:

   Loop condition 'left < right' avoids overlap [OK]

Hint: Use strict less than in loop to avoid pointer overlap [OK]

Common Mistakes:

• Using <= causes double counting at same index
• Changing comparison operators incorrectly
• Initializing max heights incorrectly

5. Given the height array {3, 0, 2, 0, 4}, what is the total trapped rain water? Explain how the trapped water is calculated step-by-step.

hard

A. 7

B. 6

C. 5

D. 8

Solution

1. Step 1: Calculate leftMax and rightMax arrays

   leftMax = [3, 3, 3, 3, 4], rightMax = [4, 4, 4, 4, 4]

2. Step 2: Calculate trapped water at each index

   Water trapped = min(leftMax[i], rightMax[i]) - height[i] = [0, 3, 1, 3, 0] Sum = 0 + 3 + 1 + 3 + 0 = 7

3. Step 3: Re-check calculation for correctness

   At index 1: min(3,4)-0=3 At index 2: min(3,4)-2=1 At index 3: min(3,4)-0=3 Sum = 7 units trapped water

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Sum trapped water = 7 units [OK]

Hint: Use leftMax and rightMax arrays to find trapped water [OK]

Common Mistakes:

• Forgetting to take minimum of leftMax and rightMax
• Subtracting height incorrectly
• Not summing trapped water at all indices