We use a stack to keep track of bars that can trap water between them. When we find a taller bar, we calculate trapped water with the bars in the stack.
Analogy: Imagine a row of walls of different heights. Water can get trapped between taller walls if there is a shorter wall in the middle. The stack helps us remember walls that might trap water until we find a taller wall to close the trap.
Goal: Calculate total trapped rain water using a stack
Step 1: Push index 0 (height 0) onto stack
stack: [0]
height: 0 1 0 2 1 0 1 3 2 1 2 1
Why: Start with first bar to compare with next bars
Step 2: Current index 1 (height 1) is taller than height at stack top (0), pop 0 and calculate trapped water
stack: []
water trapped: 0 (no left boundary yet)
Push index 1
Why: Found a taller bar, so we check if water can be trapped over popped bar
Step 3: Push index 1 (height 1) onto stack
stack: [1]
Why: Keep this bar as potential left boundary
Step 4: Current index 2 (height 0) is shorter than stack top (height 1), push index 2
stack: [1, 2]
Why: Shorter bar might trap water later
Step 5: Current index 3 (height 2) is taller than stack top (height 0), pop 2 and calculate trapped water
stack: [1]
water trapped: 1 (distance=3-1-1=1, bounded height=min(2,1)-0=1)
Continue since current height > new stack top
Why: Calculate water trapped over popped bar
Step 6: Current index 3 (height 2) is taller than stack top (height 1), pop 1 and calculate trapped water
stack: []
water trapped: 1 (no left boundary now)
Push index 3
Why: No left boundary to trap water, reset stack
Step 7: Push index 3 (height 2) onto stack
stack: [3]
Why: Keep this bar as left boundary
Step 8: Push index 4 (height 1) onto stack since shorter than top
stack: [3,4]
Why: Potential trapped water spot
Step 9: Push index 5 (height 0) onto stack since shorter than top
stack: [3,4,5]
Why: Potential trapped water spot
Step 10: Current index 6 (height 1) taller than stack top (height 0), pop 5 and calculate trapped water
stack: [3,4]
water trapped: 2 (distance=6-4-1=1, bounded height=min(1,1)-0=1)
Why: Calculate trapped water over popped bar
Step 11: Current index 6 (height 1) not taller than stack top (height 1), push index 6
stack: [3,4,6]
Why: Keep bar for future trapping
Step 12: Current index 7 (height 3) taller than stack top (height 1), pop 6 and calculate trapped water
stack: [3,4]
water trapped: 2 (distance=7-4-1=2, bounded height=min(3,1)-1=0, no water added)
Why: Check trapped water over popped bar
Step 13: Current index 7 (height 3) taller than stack top (height 1), pop 4 and calculate trapped water
stack: [3]
water trapped: 5 (distance=7-3-1=3, bounded height=min(3,2)-1=1, add 3*1=3)
Why: Calculate trapped water over popped bar
Step 14: Current index 7 (height 3) taller than stack top (height 2), pop 3 and calculate trapped water
stack: []
water trapped: 5 (no left boundary now)
Push index 7
Why: No left boundary to trap water, reset stack
Step 15: Push index 7 (height 3) onto stack
stack: [7]
Why: Keep this bar as left boundary
Step 16: Push index 8 (height 2) onto stack since shorter than top
stack: [7,8]
Why: Potential trapped water spot
Step 17: Push index 9 (height 1) onto stack since shorter than top
stack: [7,8,9]
Why: Potential trapped water spot
Step 18: Current index 10 (height 2) taller than stack top (height 1), pop 9 and calculate trapped water
stack: [7,8]
water trapped: 6 (distance=10-8-1=1, bounded height=min(2,2)-1=1)
Why: Calculate trapped water over popped bar
Step 19: Current index 10 (height 2) not taller than stack top (height 2), push index 10
stack: [7,8,10]
Why: Keep bar for future trapping
Step 20: Push index 11 (height 1) onto stack since shorter than top
stack: [7,8,10,11]
Why: Potential trapped water spot
Result:
Final trapped water: 6 units
Stack: [7,8,10,11]
Annotated Code
DSA Java
import java.util.Stack;
public class TrappingRainWater {
public static int trap(int[] height) {
int totalWater = 0;
Stack<Integer> stack = new Stack<>();
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 boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
totalWater += distance * boundedHeight;
}
stack.push(i);
}
return totalWater;
}
public static void main(String[] args) {
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
int trapped = trap(height);
System.out.println("Total trapped water: " + trapped);
}
}
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
Check if current bar is taller than top of stack to find trapped water
int top = stack.pop();
Pop the top bar which is the bottom of trapped water
if (stack.isEmpty()) { break; }
No left boundary means no trapped water, stop
int distance = i - stack.peek() - 1;
Calculate width between current bar and new top of stack
int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
Calculate height of trapped water bounded by left and right bars
totalWater += distance * boundedHeight;
Add trapped water volume for this segment
stack.push(i);
Push current bar index as potential boundary
OutputSuccess
Total trapped water: 6
Complexity Analysis
Time: O(n) because each bar is pushed and popped at most once from the stack
Space: O(n) because in worst case all bars are stored in the stack
vs Alternative: Compared to two-pointer approach which also runs in O(n) but uses constant space, stack approach is easier to understand for some but uses extra space
Edge Cases
Empty height array
Returns 0 trapped water without error
DSA Java
for (int i = 0; i < height.length; i++) {
All bars same height
No trapped water since no dips
DSA Java
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
Strictly increasing heights
No trapped water, stack grows then pops without adding water
DSA Java
if (stack.isEmpty()) { break; }
When to Use This Pattern
When you see a problem asking to find trapped water between bars or heights, and you need to efficiently find boundaries, use the stack pattern to track bars and calculate trapped water as you find taller bars.
Common Mistakes
Mistake: Not checking if stack is empty before calculating trapped water Fix: Add a check to break if stack is empty after popping to avoid errors
Mistake: Calculating distance incorrectly by not subtracting 1 Fix: Use distance = current_index - stack.peek() - 1 to get correct width
Summary
Calculates trapped rain water by using a stack to find boundaries and trapped segments.
Use when you need to find trapped water between bars efficiently in one pass.
The key insight is to use the stack to remember bars and calculate trapped water only when a taller bar closes a boundary.
Practice
(1/5)
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
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.
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.
Final Answer:
To keep track of the indices of bars that are not yet processed for water trapping -> Option A
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
Step 1: Check Java generic syntax for Stack
Java uses generics with angle brackets and wrapper classes like Integer, not primitive int.
Step 2: Identify correct initialization
Correct syntax is Stack<Integer> stack = new Stack<>(); which uses Integer wrapper and diamond operator.
Final Answer:
Stack<Integer> stack = new Stack<>(); -> Option B
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
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.
Step 2: Calculate trapped water for given input
For the input array, the total trapped water calculated is 6 units after processing all bars.
Final Answer:
6 -> Option C
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
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.
Step 2: Fix the loop condition
Changing it to 'current < height.length' prevents the out-of-bounds error and allows correct iteration.
Final Answer:
Change 'current <= height.length' to 'current < height.length' to avoid ArrayIndexOutOfBoundsException -> Option D
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
Step 1: Analyze trapped water between bars
Between bars of height 4 and 5, water is trapped over lower bars: 2, 0, 3, 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.
Final Answer:
9 -> Option A
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
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.
