Trapping Rain Water Using Stack in DSA Java - Deep Dive

Overview - Trapping Rain Water Using Stack

What is it?

Trapping Rain Water Using Stack is a method to find how much water can be trapped between bars of different heights after raining. Imagine bars of different heights placed side by side, and water fills the gaps between them. The stack helps keep track of bars that can trap water when a taller bar appears. This method efficiently calculates trapped water by using a stack data structure to remember bars that might hold water.

Why it matters

Without this method, calculating trapped water would be slow and complicated, especially for large inputs. It solves the problem of finding trapped water in linear time, which is important for performance in real-world applications like terrain analysis or building drainage systems. Without it, programs would run slower and use more resources, making them less practical.

Where it fits

Before learning this, you should understand arrays and basic stack operations. After this, you can explore other water trapping methods like two-pointer approach or dynamic programming. This topic fits into the broader study of algorithm optimization and problem-solving techniques using data structures.

Mental Model

Core Idea

Use a stack to remember bars that might trap water until a taller bar creates a boundary to calculate trapped water.

Think of it like...

Imagine stacking books of different heights on a shelf. When you place a taller book, you can see how much space is between the shorter books and the taller one, just like water trapped between bars.

Heights:  [0,1,0,2,1,0,1,3,2,1,2,1]
Stack:   ┌─────┐
         │  i  │  <-- index of bars
         └─────┘
Process: Push indexes of bars until a taller bar appears,
then pop and calculate trapped water between bars.

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem of trapping rain water between bars of different heights.

Imagine a row of bars with different heights. When it rains, water fills the gaps between these bars. The goal is to find out how much water is trapped in total. For example, if bars are [0,1,0,2], water can be trapped between the bars of height 1 and 2.

Result

You understand the problem as finding spaces between bars where water can collect.

Understanding the physical setup helps visualize why some spaces hold water and others don't.

2

Foundation

Basics of Stack Data Structure

Concept: Learn what a stack is and how it works with push and pop operations.

A stack is like a pile of plates: you add (push) plates on top and remove (pop) the top plate first. It follows Last-In-First-Out (LIFO) order. We use a stack to remember bars that might trap water until we find a taller bar.

Result

You can use a stack to keep track of bars by their indexes.

Knowing stack behavior is essential to understand how trapped water is calculated step-by-step.

3

Intermediate

Using Stack to Track Bars for Water Trapping

🤔Before reading on: do you think the stack stores bar heights or their indexes? Commit to your answer.

Concept: Use the stack to store indexes of bars and calculate trapped water when a taller bar appears.

We push indexes of bars onto the stack if the current bar is shorter or equal to the bar at the stack's top. When we find a taller bar, we pop bars from the stack and calculate trapped water between the current bar and the new top of the stack. This works because the popped bar forms the bottom of a water container.

Result

The stack helps identify boundaries and calculate trapped water efficiently.

Using indexes instead of heights allows easy calculation of width and height differences for trapped water.

4

Intermediate

Step-by-Step Dry Run of the Algorithm

🤔Before reading on: predict how much water is trapped between bars [0,1,0,2]. Commit to your answer.

Concept: Walk through the algorithm with an example to see how trapped water is calculated.

Given bars [0,1,0,2], start with an empty stack. Push index 0 (height 0). Next bar height 1 is taller, pop index 0, calculate trapped water (0 units). Push index 1. Next bar height 0 is shorter, push index 2. Next bar height 2 is taller, pop index 2, calculate trapped water between index 1 and 3 (1 unit). Push index 3. Total trapped water is 1 unit.

Result

You see how the stack helps calculate trapped water stepwise.

Dry runs reveal how the stack tracks boundaries and how trapped water accumulates.

5

Advanced

Java Implementation of Stack-Based Solution

Concept: Write complete Java code using stack to solve the trapping rain water problem.

import java.util.Stack; public class TrappingRainWater { public static int trap(int[] height) { int water = 0; Stack stack = new Stack<>(); for (int i = 0; i < height.length; i++) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int bottom = stack.pop(); if (stack.isEmpty()) break; int distance = i - stack.peek() - 1; int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[bottom]; water += distance * boundedHeight; } stack.push(i); } return water; } public static void main(String[] args) { int[] bars = {0,1,0,2,1,0,1,3,2,1,2,1}; System.out.println(trap(bars)); } }

Result

Output: 6

Seeing the full code connects the theory to practical implementation and confirms correctness.

6

Expert

Why Stack Approach is Efficient and Its Limitations

🤔Before reading on: do you think the stack method always uses less memory than two-pointer approach? Commit to your answer.

Concept: Analyze the time and space complexity and compare with other methods.

The stack method runs in O(n) time because each bar is pushed and popped at most once. It uses O(n) space for the stack in the worst case. Compared to the two-pointer method, which uses O(1) space, stack method is easier to understand but uses more memory. It is efficient for large inputs but may not be best if memory is very limited.

Result

You understand trade-offs between stack and other approaches.

Knowing efficiency and limits helps choose the right method for different scenarios.

Under the Hood

The stack stores indexes of bars in non-increasing order of height. When a taller bar arrives, it means water can be trapped over the bars popped from the stack. The popped bar forms the bottom of a container, and the current bar and the new top of the stack form the boundaries. The trapped water volume is calculated by width (distance between boundaries minus one) times height (minimum boundary height minus bottom bar height).

Why designed this way?

This method was designed to achieve linear time complexity by avoiding repeated scanning of bars. Using a stack to remember bars waiting for a taller boundary avoids nested loops. Alternatives like brute force check all pairs but are slower. The stack approach balances simplicity and efficiency.

Input bars:  [0,1,0,2,1,0,1,3,2,1,2,1]
Stack process:
 i=0 push 0
 i=1 height[1]>height[0], pop 0, no left boundary, push 1
 i=2 push 2
 i=3 height[3]>height[2], pop 2, calculate water
       height[3]>height[1], pop 1, calculate water
 push 3
 ...
Stack helps find boundaries and trapped water stepwise.

Myth Busters - 3 Common Misconceptions

Quick: Does the stack store bar heights directly or their indexes? Commit to your answer.

Common Belief: The stack stores the heights of bars to calculate trapped water.

Reality: The stack stores indexes of bars, not their heights, to calculate distances and heights accurately.

Why it matters: Storing heights instead of indexes makes it impossible to calculate the width between bars, leading to incorrect trapped water calculation.

Quick: Does trapped water depend only on the tallest bar? Commit to yes or no.

Common Belief: Trapped water depends only on the tallest bar in the array.

Reality: Trapped water depends on local boundaries formed by bars on both sides, not just the tallest bar overall.

Why it matters: Ignoring local boundaries causes underestimation or overestimation of trapped water.

Quick: Is the stack method always more memory efficient than two-pointer approach? Commit to yes or no.

Common Belief: Stack method always uses less memory than other methods.

Reality: Stack method uses O(n) extra space, which can be more than the two-pointer method's O(1) space.

Why it matters: Choosing stack method without considering memory can cause issues in memory-constrained environments.

Expert Zone

1

The stack maintains indexes in a way that bars are always in non-increasing height order, which is crucial for correct water calculation.

2

When popping from the stack, if it becomes empty, it means no left boundary exists, so no water is trapped for that segment.

3

The calculation uses the minimum of current and stack top bar heights to handle uneven boundaries correctly.

When NOT to use

Avoid using stack method when memory is very limited; prefer the two-pointer approach which uses constant space. Also, for streaming data or very large inputs where random access is costly, other methods might be better.

Production Patterns

In real systems, this method is used in terrain modeling, flood simulation, and architectural drainage design where quick and accurate water trapping calculations are needed. It is also a common interview problem to test stack usage and problem-solving skills.

Connections

Two-Pointer Technique

Alternative approach to solve the same problem with different space-time tradeoffs.

Understanding stack method deepens comprehension of two-pointer approach by contrasting how boundaries are tracked.

Histogram Largest Rectangle Problem

Uses a similar stack-based approach to find largest rectangle in histogram bars.

Recognizing the shared stack pattern helps reuse problem-solving strategies across different challenges.

Civil Engineering Drainage Systems

Real-world application of water trapping concepts in designing drainage and flood control.

Knowing algorithmic water trapping connects to practical engineering problems of managing water flow and storage.

Common Pitfalls

#1 Pushing bar heights instead of indexes onto the stack.

Wrong approach:

Stack stack = new Stack<>();
for (int h : height) {
while (!stack.isEmpty() && h > stack.peek()) {
stack.pop();
}
stack.push(h);
}

Correct approach:

Stack stack = new Stack<>();
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
stack.pop();
}
stack.push(i);
}

Root cause:

Confusing the need for indexes to calculate width with storing heights directly.

#2 Calculating trapped water without checking if stack is empty after popping.

Wrong approach:

while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int bottom = stack.pop();
int distance = i - stack.peek() - 1; // No check if stack is empty
int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[bottom];
water += distance * boundedHeight;
}

Correct approach:

while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int bottom = stack.pop();
if (stack.isEmpty()) break;
int distance = i - stack.peek() - 1;
int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[bottom];
water += distance * boundedHeight;
}

Root cause:

Not handling the case where no left boundary exists leads to errors or exceptions.

#3 Using nested loops to check all pairs of bars for trapped water.

Wrong approach:

int water = 0;
for (int i = 0; i < height.length; i++) {
for (int j = i + 1; j < height.length; j++) {
// complex checks
}
}

Correct approach:

Use stack or two-pointer method to achieve linear time complexity.

Root cause:

Not knowing efficient algorithms leads to slow, impractical solutions.

Key Takeaways

Trapping Rain Water Using Stack efficiently calculates trapped water by remembering bars that form boundaries.

The stack stores indexes, not heights, to calculate distances and heights for trapped water correctly.

Each bar is pushed and popped at most once, making the algorithm run in linear time.

Handling edge cases like empty stack after popping is crucial to avoid errors.

Understanding this method helps solve similar problems and improves algorithmic thinking.

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