Trapping Rain Water Problem in DSA Java - Build from Scratch

Trapping Rain Water Problem

📖 Scenario: Imagine you have a row of walls with different heights. When it rains, water gets trapped between these walls. You want to find out how much water is trapped after the rain stops.

🎯 Goal: Build a Java program that calculates the total amount of trapped rainwater given an array of wall heights.

📋 What You'll Learn

Create an integer array called heights with the exact values {0,1,0,2,1,0,1,3,2,1,2,1}

Create two integer arrays called leftMax and rightMax to store the maximum wall heights from the left and right sides

Use a for loop to fill leftMax with the maximum height to the left of each position

Use a for loop to fill rightMax with the maximum height to the right of each position

Calculate the trapped water at each position using the minimum of leftMax and rightMax minus the height at that position

Sum all trapped water amounts into an integer variable called totalWater

Print the value of totalWater

💡 Why This Matters

🌍 Real World

Calculating trapped rainwater helps in designing drainage systems and understanding water flow in urban planning.

💼 Career

This problem is a common coding interview question that tests understanding of arrays, loops, and problem-solving skills.

1

Create the heights array

Create an integer array called heights with these exact values: {0,1,0,2,1,0,1,3,2,1,2,1}

DSA Java

// Create the heights array with given values
// Your code here

Hint

Use int[] heights = { ... }; to create the array with the exact numbers.

2

Create leftMax and rightMax arrays

Create two integer arrays called leftMax and rightMax with the same length as heights

DSA Java

public class TrappingRainWater {
    public static void main(String[] args) {
        int[] heights = {0,1,0,2,1,0,1,3,2,1,2,1};
        // Create leftMax and rightMax arrays
        // Your code here
    }
}

Hint

Use new int[n] to create arrays with the same length as heights.

3

Fill leftMax and rightMax arrays

Use a for loop with variable i from 0 to n-1 to fill leftMax so that each element is the maximum height to the left including current. Then use a for loop with variable i from n-1 down to 0 to fill rightMax so each element is the maximum height to the right including current.

DSA Java

public class TrappingRainWater {
    public static void main(String[] args) {
        int[] heights = {0,1,0,2,1,0,1,3,2,1,2,1};
        int n = heights.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        // Fill leftMax array
        // Your code here
        // Fill rightMax array
        // Your code here
    }
}

Hint

Remember to initialize the first element of leftMax and the last element of rightMax before the loops.

4

Calculate and print total trapped water

Create an integer variable called totalWater and set it to 0. Use a for loop with variable i from 0 to n-1 to add the trapped water at each position to totalWater. The trapped water at position i is the minimum of leftMax[i] and rightMax[i] minus heights[i]. Finally, print totalWater.

DSA Java

public class TrappingRainWater {
    public static void main(String[] args) {
        int[] heights = {0,1,0,2,1,0,1,3,2,1,2,1};
        int n = heights.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = heights[0];
        for (int i = 1; i = 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], heights[i]);
        }

        // Calculate total trapped water and print it
        // Your code here
    }
}

Hint

Use System.out.println(totalWater); to print the final result.

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