Trapping Rain Water Using Stack in DSA Rust

Mental Model

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.

height array: [0,1,0,2,1,0,1,3,2,1,2,1]
stack: bottom -> top
Initially empty: []
Water trapped shown as ~ between bars:

 3 |       |       |
 2 |     | |   | | |
 1 | |   | | | | | |
 0 | | | | | | | | |
    0 1 2 3 4 5 6 7 8 9 10 11

Dry Run Walkthrough

Input: height array: [0,1,0,2,1,0,1,3,2,1,2,1]

Goal: Calculate total units of water trapped between bars using a stack

Step 1: Push index 0 (height 0) onto stack

stack: [0]
water trapped: 0

Why: Start with first bar to compare with next bars

Step 2: Push index 1 (height 1) since height[1] > height[0]

stack: [0,1]
water trapped: 0

Why: Current bar taller, so push to stack to find trapping later

Step 3: Index 2 (height 0) is less than height at stack top (1), push 2

stack: [0,1,2]
water trapped: 0

Why: Lower bar might trap water later, keep it in stack

Step 4: Index 3 (height 2) is taller than height at stack top (0 at index 2), pop 2 and calculate trapped water

stack after pop: [0,1]
Calculate distance=3-1-1=1, bounded height=min(2,1)-0=1
Water trapped += 1*1=1
Push index 3
stack: [0,1,3]
water trapped: 1

Why: Found right boundary taller than bottom, so water trapped between

Step 5: Index 4 (height 1) less than top height (2), push 4

stack: [0,1,3,4]
water trapped: 1

Why: Lower bar might trap water later

Step 6: Index 5 (height 0) less than top height (1), push 5

stack: [0,1,3,4,5]
water trapped: 1

Why: Keep lower bar for future trapping

Step 7: Index 6 (height 1) taller than top (0 at 5), pop 5 and calculate trapped water

stack after pop: [0,1,3,4]
Distance=6-4-1=1, bounded height=min(1,1)-0=1
Water trapped +=1*1=1+1=2
Push 6
stack: [0,1,3,4,6]
water trapped: 2

Why: Water trapped between bars at 4 and 6 over popped bar 5

Step 8: Index 7 (height 3) taller than top (1 at 6), pop 6 and calculate water

stack after pop: [0,1,3,4]
Distance=7-4-1=2, bounded height=min(3,1)-1=0
Water trapped += 0
Then pop 4 (height 1), distance=7-3-1=3, bounded height=min(3,2)-1=1
Water trapped += 3*1=2+3=5
Then pop 3 (height 2), distance=7-1-1=5, bounded height=min(3,1)-2=-1 (0)
Water trapped += 0
Push 7
stack: [0,1,7]
water trapped: 5

Why: Multiple pops to calculate trapped water with taller right boundary

Step 9: Index 8 (height 2) less than top (3), push 8

stack: [0,1,7,8]
water trapped: 5

Why: Lower bar might trap water later

Step 10: Index 9 (height 1) less than top (2), push 9

stack: [0,1,7,8,9]
water trapped: 5

Why: Keep for future trapping

Step 11: Index 10 (height 2) taller than top (1 at 9), pop 9 and calculate water

stack after pop: [0,1,7,8]
Distance=10-8-1=1, bounded height=min(2,2)-1=1
Water trapped +=1*1=5+1=6
Push 10
stack: [0,1,7,8,10]
water trapped: 6

Why: Water trapped between bars at 8 and 10 over popped bar 9

Step 12: Index 11 (height 1) less than top (2), push 11

stack: [0,1,7,8,10,11]
water trapped: 6

Why: Lower bar might trap water later

Result:

Final stack: [0,1,7,8,10,11]
Total water trapped: 6 units

Annotated Code

DSA Rust

struct Solution;

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let mut stack: Vec<usize> = Vec::new();
        let mut water = 0;
        for i in 0..height.len() {
            while !stack.is_empty() && height[i] > height[*stack.last().unwrap()] {
                let top = stack.pop().unwrap();
                if stack.is_empty() {
                    break;
                }
                let distance = i - stack.last().unwrap() - 1;
                let bounded_height = height[i].min(height[*stack.last().unwrap()]) - height[top];
                water += (distance as i32) * bounded_height;
            }
            stack.push(i);
        }
        water
    }
}

fn main() {
    let height = vec![0,1,0,2,1,0,1,3,2,1,2,1];
    let result = Solution::trap(height);
    println!("{}", result);
}

while !stack.is_empty() && height[i] > height[*stack.last().unwrap()] {

Check if current bar is taller than top bar in stack to find right boundary

let top = stack.pop().unwrap();

Pop the top bar which is the bottom of trapped water

if stack.is_empty() { break; }

No left boundary if stack empty, so stop

let distance = i - stack.last().unwrap() - 1;

Calculate horizontal distance between left and right boundaries

let bounded_height = height[i].min(height[*stack.last().unwrap()]) - height[top];

Calculate height of trapped water bounded by shorter boundary

water += (distance as i32) * bounded_height;

Add trapped water volume for this segment

stack.push(i);

Push current bar index to stack for future trapping

Output

6

Complexity Analysis

Time: O(n) because each bar is pushed and popped at most once

Space: O(n) for the stack in worst case when bars are in ascending order

vs Alternative: Compared to two-pointer approach which also runs in O(n), stack method is easier to understand for some but uses extra space

Edge Cases

Empty height array

Returns 0 as no bars to trap water

DSA Rust

for i in 0..height.len() {

All bars same height

No water trapped, returns 0

DSA Rust

while !stack.is_empty() && height[i] > height[*stack.last().unwrap()] {

Strictly increasing bars

Stack grows, no water trapped, returns 0

DSA Rust

stack.push(i);

When to Use This Pattern

When you see a problem asking how much water can be trapped between bars or heights, consider the stack pattern to track boundaries and calculate trapped water efficiently.

Common Mistakes

Mistake: Not checking if stack is empty before accessing last element after pop
Fix: Add a check to break the loop if stack becomes empty after popping

Mistake: Calculating distance or bounded height incorrectly by mixing indices
Fix: Use correct indices from stack and current position to calculate distance and bounded height

Summary

Calculates trapped rain water between bars using a stack to find boundaries.

Use when you need to find trapped water volume efficiently in one pass.

The stack helps remember bars that can trap water until a taller bar closes the trap.

Practice

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

easy

A. To reverse the order of the bars

B. To store the total amount of trapped water

C. To keep track of bars that are not yet processed for water trapping

D. To sort the heights of bars in ascending order

Solution

1. Step 1: Understand the role of stack in the algorithm

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

2. Step 2: Clarify what the stack does not do

   The stack does not store water amount or sort bars; it helps find boundaries for trapped water.

3. Final Answer:

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

4. Quick Check:

   Stack tracks bars for trapping water = D [OK]

Hint: Stack holds bars waiting for right boundary [OK]

Common Mistakes:

• Thinking stack stores water amount
• Assuming stack sorts the bars
• Believing stack reverses bar order

2. Which of the following Rust code snippets correctly declares an empty stack to use in the trapping rain water algorithm?

easy

A. let stack = Vec::with_capacity(10);

B. let mut stack: Vec<usize> = Vec::new();

C. let stack = vec![0];

D. let mut stack: Vec<i32> = Vec::new();

Solution

1. Step 1: Identify correct stack declaration for indices

   Indices are usize type, so stack must be Vec<usize> and mutable to push/pop.

2. Step 2: Check each option

   let mut stack: Vec<usize> = Vec::new(); correctly declares mutable Vec<usize> empty stack. let stack = Vec::with_capacity(10); is immutable and no mut keyword. let stack = vec![0]; initializes with one element, not empty. let mut stack: Vec<i32> = Vec::new(); uses i32 instead of usize for indices.

3. Final Answer:

   let mut stack: Vec<usize> = Vec::new(); -> Option B

4. Quick Check:

   Mutable Vec<usize> empty stack = A [OK]

Hint: Use mutable Vec<usize> for stack of indices [OK]

Common Mistakes:

• Using wrong type like i32 for indices
• Not making stack mutable
• Initializing stack with elements instead of empty

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

fn trap(height: Vec<i32>) -> i32 {
    let mut stack: Vec<usize> = Vec::new();
    let mut water = 0;
    for i in 0..height.len() {
        while !stack.is_empty() && height[i] > height[*stack.last().unwrap()] {
            let top = stack.pop().unwrap();
            if stack.is_empty() {
                break;
            }
            let distance = i - *stack.last().unwrap() - 1;
            let bounded_height = height[i].min(height[*stack.last().unwrap()]) - height[top];
            water += (distance as i32) * bounded_height;
        }
        stack.push(i);
    }
    water
}

let heights = vec![0,1,0,2,1,0,1,3,2,1,2,1];
println!("{}", trap(heights));

medium

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Understand the input and algorithm

   The input heights represent bars: [0,1,0,2,1,0,1,3,2,1,2,1]. The stack-based algorithm calculates trapped water by finding bounded areas.

2. Step 2: Calculate trapped water step-by-step

   The known trapped water for this input is 6 units, as the algorithm sums water trapped between bars correctly.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Trapped water for given heights = 6 [OK]

Hint: Known test case result is 6 units trapped water [OK]

Common Mistakes:

• Miscounting trapped water units
• Ignoring boundary conditions
• Incorrectly calculating distance or height

4. Identify the bug in the following Rust code snippet for trapping rain water using stack and select the fix:

fn trap(height: Vec<i32>) -> i32 {
    let mut stack: Vec<usize> = Vec::new();
    let mut water = 0;
    for i in 0..height.len() {
        while !stack.is_empty() && height[i] > height[*stack.last().unwrap()] {
            let top = stack.pop().unwrap();
            if stack.is_empty() {
                break;
            }
            let distance = i - *stack.last().unwrap() - 1;
            let bounded_height = height[i].min(height[*stack.last().unwrap()]) - height[top];
            water += distance * bounded_height;
        }
        stack.push(i);
    }
    water
}

medium

A. Change height[i] > height[stack.last().unwrap()] to height[i] >= height[stack.last().unwrap()]

B. Change stack.pop().unwrap() to stack.pop();

C. Remove the if stack.is_empty() { break; } check

D. Change water += distance * bounded_height; to water += (distance as i32) * bounded_height;

Solution

1. Step 1: Identify type mismatch in multiplication

   distance is usize, bounded_height is i32; multiplying usize * i32 causes type error in Rust.

2. Step 2: Fix by casting distance to i32 before multiplication

   Cast distance as i32: (distance as i32) * bounded_height to fix type mismatch.

3. Final Answer:

   Change water += distance * bounded_height; to water += (distance as i32) * bounded_height; -> Option D

4. Quick Check:

   Cast usize to i32 before multiply = C [OK]

Hint: Cast usize to i32 before multiplying [OK]

Common Mistakes:

• Ignoring type mismatch errors
• Removing necessary empty stack check
• Changing comparison operator incorrectly

5. Given the heights array [4, 2, 0, 3, 2, 5], what is the total trapped rain water calculated by the stack-based algorithm?

hard

A. 9

B. 8

C. 6

D. 7

Solution

1. Step 1: Visualize the bars and trapped water

   Bars heights: 4, 2, 0, 3, 2, 5. Water trapped between bars is calculated by stack algorithm using boundaries.

2. Step 2: Calculate trapped water stepwise

   Using min(left_max, right_max) - height[i] for each i:
   - i=1: min(4,5)-2=2
   - i=2: min(4,5)-0=4
   - i=3: min(4,5)-3=1
   - i=4: min(4,5)-2=2
   Total trapped water = 9 units.

3. Final Answer:

   9 -> Option A

4. Quick Check:

   Sum trapped water units = 9 [OK]

Hint: Sum water trapped between boundaries carefully [OK]

Common Mistakes:

• Miscounting water units between bars
• Ignoring zero height bars
• Not considering both left and right boundaries