Trapping Rain Water Using Stack in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trapping Rain Water Calculation

What is the output of the following Java code that calculates trapped rain water using a stack?

DSA Java

import java.util.Stack;

public class RainWater {
    public static int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int water = 0, current = 0;
        while (current < height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;
                int distance = current - stack.peek() - 1;
                int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top];
                water += distance * bounded_height;
            }
            stack.push(current++);
        }
        return water;
    }

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }
}

A 5

B 6

C 7

D 8

💡 Hint

Trace the stack operations and calculate trapped water between bars.

The code uses a stack to find boundaries and calculates trapped water between them. For the given input, the total trapped water is 6 units.

🧠 Conceptual

intermediate

Understanding Stack Usage in Trapping Rain Water

Why is a stack used in the trapping rain water problem instead of a simple loop?

A To keep track of bars that can form boundaries for trapped water

B To sort the bars in ascending order

C To store the total water trapped at each index

D To reverse the height array for easier calculation

💡 Hint

Think about how boundaries for water trapping are identified.

The stack helps keep indices of bars that might form boundaries. When a higher bar is found, it helps calculate trapped water between boundaries.

🔧 Debug

advanced

Identify the Error in Modified Trapping Rain Water Code

What error will occur when running this modified Java code for trapping rain water?

DSA Java

import java.util.Stack;

public class RainWater {
    public static int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int water = 0, current = 0;
        while (current <= height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;
                int distance = current - stack.peek() - 1;
                int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top];
                water += distance * bounded_height;
            }
            stack.push(current++);
        }
        return water;
    }

    public static void main(String[] args) {
        int[] height = {4,2,0,3,2,5};
        System.out.println(trap(height));
    }
}

A No error, outputs 9

B NullPointerException

C ArrayIndexOutOfBoundsException

D Infinite loop

💡 Hint

Check the loop condition and array access.

The loop condition uses <= height.length which causes current to go out of array bounds, leading to ArrayIndexOutOfBoundsException.

🚀 Application

advanced

Calculate Trapped Water for Custom Input

Given the height array {3, 0, 2, 0, 4}, what is the total trapped rain water calculated by the stack method?

A 6

B 4

C 5

D 7

💡 Hint

Visualize the bars and trapped water between them.

Water trapped is 7 units in total between the bars.

❓ Predict Output

expert

Output of Trapping Rain Water with Edge Case Input

What is the output of the following Java code for trapping rain water when input is strictly increasing heights?

DSA Java

import java.util.Stack;

public class RainWater {
    public static int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int water = 0, current = 0;
        while (current < height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;
                int distance = current - stack.peek() - 1;
                int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top];
                water += distance * bounded_height;
            }
            stack.push(current++);
        }
        return water;
    }

    public static void main(String[] args) {
        int[] height = {1, 2, 3, 4, 5};
        System.out.println(trap(height));
    }
}

A 0

B 4

C 10

D 5

💡 Hint

Strictly increasing bars cannot trap water.

Since bars increase strictly, no water can be trapped between them, so output is 0.

Practice

1. What is the main purpose of using a stack in the Trapping Rain Water Using Stack algorithm?

easy

A. To keep track of the indices of bars that are not yet processed for water trapping

B. To store the heights of the bars in sorted order

C. To reverse the array of bar heights

D. To count the total number of bars

Solution

1. Step 1: Understand the role of the stack

   The stack stores indices of bars that are waiting to find a right boundary to trap water.

2. Step 2: Explain how the stack helps in trapping water

   When a bar taller than the top of the stack is found, it means water can be trapped between bars. The stack helps find the left boundary and calculate trapped water.

3. Final Answer:

   To keep track of the indices of bars that are not yet processed for water trapping -> Option A

4. Quick Check:

   Stack stores indices for trapping water = C [OK]

Hint: Stack holds indices to find boundaries for trapped water [OK]

Common Mistakes:

• Thinking stack stores heights instead of indices
• Assuming stack sorts bars by height
• Confusing stack use with reversing the array

2. Which of the following Java code snippets correctly initializes an empty stack to be used for trapping rain water indices?

easy

A. Stack stack = new Stack<int>();

B. Stack<Integer> stack = new Stack<>();

C. Stack<int> stack = new Stack<>();

D. Stack<Integer> stack = new Stack<int>();

Solution

1. Step 1: Check Java generic syntax for Stack

   Java uses generics with angle brackets and wrapper classes like Integer, not primitive int.

2. Step 2: Identify correct initialization

   Correct syntax is Stack<Integer> stack = new Stack<>(); which uses Integer wrapper and diamond operator.

3. Final Answer:

   Stack<Integer> stack = new Stack<>(); -> Option B

4. Quick Check:

   Use wrapper Integer and diamond operator = A [OK]

Hint: Use Stack<Integer> with diamond operator for empty stack [OK]

Common Mistakes:

• Using primitive int inside generics
• Omitting generic type causing raw type warning
• Incorrect constructor syntax with generics

3. What is the output of the following Java code snippet that calculates trapped rain water using stack?

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) {
    Stack<Integer> stack = new Stack<>();
    int water = 0, current = 0;
    while (current < height.length) {
        while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
            int top = stack.pop();
            if (stack.isEmpty()) break;
            int distance = current - stack.peek() - 1;
            int boundedHeight = Math.min(height[current], height[stack.peek()]) - height[top];
            water += distance * boundedHeight;
        }
        stack.push(current++);
    }
    return water;
}

medium

A. 5

B. 7

C. 6

D. 8

Solution

1. Step 1: Trace the stack and water calculation

   The code uses a stack to find boundaries and calculates trapped water step-by-step for the given heights.

2. Step 2: Calculate trapped water for given input

   For the input array, the total trapped water calculated is 6 units after processing all bars.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Trapped water for given heights = 6 [OK]

Hint: Trace stack pops and water increments carefully [OK]

Common Mistakes:

• Miscounting distance between bars
• Incorrect bounded height calculation
• Forgetting to break when stack is empty

4. Identify the error in the following Java code snippet for trapping rain water using stack and select the fix.

public static int trap(int[] height) {
    Stack<Integer> stack = new Stack<>();
    int water = 0, current = 0;
    while (current <= height.length) {
        while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
            int top = stack.pop();
            if (stack.isEmpty()) break;
            int distance = current - stack.peek() - 1;
            int boundedHeight = Math.min(height[current], height[stack.peek()]) - height[top];
            water += distance * boundedHeight;
        }
        stack.push(current++);
    }
    return water;
}

medium

A. Change 'stack.pop()' to 'stack.peek()' to avoid removing elements

B. Replace Stack<Integer> with ArrayList<Integer> for better performance

C. Remove the inner while loop to simplify the code

D. Change 'current <= height.length' to 'current < height.length' to avoid ArrayIndexOutOfBoundsException

Solution

1. Step 1: Identify the loop boundary error

   The condition 'current <= height.length' causes an attempt to access height[height.length], which is out of bounds.

2. Step 2: Fix the loop condition

   Changing it to 'current < height.length' prevents the out-of-bounds error and allows correct iteration.

3. Final Answer:

   Change 'current <= height.length' to 'current < height.length' to avoid ArrayIndexOutOfBoundsException -> Option D

4. Quick Check:

   Loop boundary must be less than array length = A [OK]

Hint: Use '<' for array index loops to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Replacing stack with wrong data structure
• Removing necessary inner loop

5. Given the array height = {4, 2, 0, 3, 2, 5}, what is the total amount of trapped rain water calculated by the stack-based algorithm?

hard

A. 9

B. 7

C. 10

D. 8

Solution

1. Step 1: Analyze trapped water between bars

   Between bars of height 4 and 5, water is trapped over lower bars: 2, 0, 3, 2.

2. Step 2: Calculate trapped water volume

   Water level is min(4,5)=4. Water trapped = (4-2) + (4-0) + (4-3) + (4-2) = 2 + 4 + 1 + 2 = 9 units.

3. Final Answer:

   9 -> Option A

4. Quick Check:

   Sum trapped water between boundaries = 9 [OK]

Hint: Calculate water trapped between boundaries using min height [OK]

Common Mistakes:

• Using left boundary height only
• Ignoring right boundary taller bar
• Adding heights instead of differences