Trapping Rain Water Problem in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the left max array for trapping rain water.

DSA Java

int[] leftMax = new int[height.length];
leftMax[0] = height[0];
for (int i = 1; i < height.length; i++) {
    leftMax[i] = Math.[1](leftMax[i - 1], height[i]);
}

Drag options to blanks, or click blank then click option'

Amax

Bmin

Cabs

Dsum

Attempts:

3 left

💡 Hint

Common Mistakes

Using Math.min instead of Math.max

Using addition instead of comparison

We use Math.max to keep track of the highest bar from the left side at each position.

2fill in blank

medium

Complete the code to initialize the right max array for trapping rain water.

DSA Java

int[] rightMax = new int[height.length];
rightMax[height.length - 1] = height[height.length - 1];
for (int i = height.length - 2; i >= 0; i--) {
    rightMax[i] = Math.[1](rightMax[i + 1], height[i]);
}

Drag options to blanks, or click blank then click option'

Amax

Bmin

Cabs

Dsum

Attempts:

3 left

💡 Hint

Common Mistakes

Using Math.min instead of Math.max

Using addition instead of comparison

We use Math.max to keep track of the highest bar from the right side at each position.

3fill in blank

hard

Fix the error in calculating trapped water at each position.

DSA Java

int water = 0;
for (int i = 0; i < height.length; i++) {
    water += Math.min(leftMax[i], rightMax[i]) - [1];
}

Drag options to blanks, or click blank then click option'

ArightMax[i]

BleftMax[i]

Cheight[i]

Dwater

Attempts:

3 left

💡 Hint

Common Mistakes

Subtracting leftMax or rightMax instead of height

Subtracting water variable itself

We subtract the height of the current bar to find trapped water at that position.

4fill in blank

hard

Fill both blanks to complete the trapping rain water calculation loop.

DSA Java

int water = 0;
for (int i = 0; i < height.length; i++) {
    int minHeight = Math.[1](leftMax[i], rightMax[i]);
    water += minHeight - [2];
}

Drag options to blanks, or click blank then click option'

Amin

Bheight[i]

Cmax

Dwater

Attempts:

3 left

💡 Hint

Common Mistakes

Using Math.max instead of Math.min for minHeight

Subtracting wrong variable instead of height[i]

We find the minimum of leftMax and rightMax, then subtract the current height to get trapped water.

5fill in blank

hard

Fill all three blanks to complete the trapping rain water function.

DSA Java

public int trap(int[] height) {
    int n = height.length;
    int[] leftMax = new int[n];
    int[] rightMax = new int[n];
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.[1](leftMax[i - 1], height[i]);
    }
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.[2](rightMax[i + 1], height[i]);
    }
    int water = 0;
    for (int i = 0; i < n; i++) {
        water += Math.min(leftMax[i], rightMax[i]) - [3];
    }
    return water;
}

Drag options to blanks, or click blank then click option'

Amax

Bheight[i]

Cmin

Dsum

Attempts:

3 left

💡 Hint

Common Mistakes

Using Math.min instead of Math.max for leftMax or rightMax

Subtracting wrong variable instead of height[i]

We use Math.max to build leftMax and rightMax arrays, then subtract height[i] to calculate trapped water.

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