Trapping Rain Water Using Stack in DSA Java - Execution Trace

Concept Flow - Trapping Rain Water Using Stack

Start with empty stack

↓

Iterate over height array

↓

While stack not empty and current height > height at stack top

↓

Pop top

↓

Calculate trapped water

↓

Push current index to stack

↓

Repeat until end

↓

Return total trapped water

We scan the height array, using a stack to keep indices of bars. When we find a bar taller than the top of the stack, we pop and calculate trapped water between bars.

Execution Sample

DSA Java

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

Calculates trapped rain water by using a stack to find boundaries and heights where water can be trapped.

Execution Table

Step	Operation	Stack Content (indices)	Current Index i	Height[i]	Action	Water Trapped So Far	Visual State
1	Start	[]	-	-	Initialize stack and water=0	0	[]
2	i=0	[0]	0	0	Push index 0	0	[0:0]
3	i=1	[0,1]	1	1	Push index 1	0	[0:0,1:1]
4	i=2	[0,1,2]	2	0	Push index 2	0	[0:0,1:1,2:0]
5	i=3	[0,2,3]	3	2	Pop 1 (height 1), calculate water: distance=3-0-1=2, bounded_height=min(2,0)-1= -1 (no water), then push 3	0	[0:0,2:0,3:2]
6	i=4	[0,2,3,4]	4	1	Push index 4	0	[0:0,2:0,3:2,4:1]
7	i=5	[0,2,3,4,5]	5	0	Push index 5	0	[0:0,2:0,3:2,4:1,5:0]
8	i=6	[0,2,3,4,6]	6	1	Pop 5 (height 0), calculate water: distance=6-4-1=1, bounded_height=min(1,1)-0=1, water=1	1	[0:0,2:0,3:2,4:1,6:1]
9	i=6	[0,2,3,6]	6	1	Pop 4 (height 1), no water added (bounded_height=0)	1	[0:0,2:0,3:2,6:1]
10	i=6	[0,2,3,6]	6	1	Push index 6	1	[0:0,2:0,3:2,6:1]
11	i=7	[0,2,3,6,7]	7	2	Push index 7	1	[0:0,2:0,3:2,6:1,7:2]
12	i=8	[0,2,3,6,7,8]	8	1	Push index 8	1	[0:0,2:0,3:2,6:1,7:2,8:1]
13	i=9	[0,2,3,6,7,9]	9	2	Pop 8 (height 1), calculate water: distance=9-7-1=1, bounded_height=min(2,2)-1=1, water=2	2	[0:0,2:0,3:2,6:1,7:2,9:2]
14	i=9	[0,2,3,6,7,9]	9	2	Push index 9	2	[0:0,2:0,3:2,6:1,7:2,9:2]
15	i=10	[0,2,3,6,7,9,10]	10	1	Push index 10	2	[0:0,2:0,3:2,6:1,7:2,9:2,10:1]
16	i=11	[0,2,3,6,7,9,11]	11	2	Pop 10 (height 1), calculate water: distance=11-9-1=1, bounded_height=min(2,2)-1=1, water=3	3	[0:0,2:0,3:2,6:1,7:2,9:2,11:2]
17	i=11	[0,2,3,6,7,9,11]	11	2	Push index 11	3	[0:0,2:0,3:2,6:1,7:2,9:2,11:2]
18	End	[0,2,3,6,7,9,11]	-	-	End of array reached	3	[0:0,2:0,3:2,6:1,7:2,9:2,11:2]

💡 Reached end of height array, total trapped water calculated

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	After Step 13	After Step 16	Final
stack	[]	[0]	[0,1,2]	[0,2,3,4,6]	[0,2,3,6,7,9]	[0,2,3,6,7,9,11]	[0,2,3,6,7,9,11]
water	0	0	0	1	2	3	3
i	-	0	2	6	9	11	End

Key Moments - 3 Insights

Why do we pop from the stack only when current height is greater than height at stack top?

Because popping happens only when we find a right boundary taller than the bar at stack top, allowing us to calculate trapped water between boundaries. See execution_table steps 8 and 13 where popping triggers water calculation.

Why do we check if the stack is empty after popping before calculating water?

If the stack is empty after popping, it means no left boundary exists to trap water, so we skip calculation. This is shown in execution_table step 8 where we break if stack is empty.

How is the distance between bars calculated for trapped water?

Distance is the horizontal gap between current index and new stack top minus one (i - stack.peek() - 1). This is used in execution_table step 8 to find how many bars wide the trapped water is.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the amount of water trapped after popping index 5?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Water Trapped So Far' column at step 8 in execution_table.

At which step does the trapped water total first increase from 0 to a positive value?

A Step 4

B Step 8

C Step 13

D Step 16

💡 Hint

Look at the 'Water Trapped So Far' column in execution_table and find when it changes from 0 to positive.

If the height at index 6 was increased, how would that affect the trapped water at step 8?

A Water trapped would increase

B Water trapped would decrease

C Water trapped would stay the same

D Stack would be empty

💡 Hint

Consider how bounded_height depends on min(height[i], height[stack.peek()]) and how increasing height[6] affects it at step 8.

Concept Snapshot

Trapping Rain Water Using Stack:
- Use a stack to store indices of bars
- Iterate over heights, pop when current bar is taller
- Calculate trapped water using distance and bounded height
- Push current index after popping
- Sum trapped water and return total

Full Transcript

This visualization shows how to calculate trapped rain water using a stack. We start with an empty stack and iterate over the height array. For each bar, if it is taller than the bar at the top of the stack, we pop from the stack and calculate trapped water between the current bar and the new top of the stack. We keep track of the total water trapped. The stack stores indices of bars that form boundaries for trapping water. The process continues until we reach the end of the array, and the total trapped water is returned.

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