Trapping Rain Water Using Stack in DSA Rust - 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 from stack as bottom

↓

If stack empty after pop, break loop

↓

Calculate distance between current and new stack top

↓

Calculate bounded height

↓

Add trapped water: distance * bounded height

↓

Push current index to stack

↓

Repeat until end of array

↓

Return total trapped water

We use a stack to keep track of bars. When a taller bar comes, we pop shorter bars and calculate trapped water between the current bar and the new top of stack.

Execution Sample

DSA Rust

let height: Vec<i32> = vec![0,1,0,2,1,0,1,3,2,1,2,1];
let mut stack: Vec<usize> = Vec::new();
let mut water: i32 = 0;
for i in 0..height.len() {
    while let Some(&top) = stack.last() {
        if height[i] > height[top] {
            let bottom = stack.pop().unwrap();
            if let Some(&left) = stack.last() {
                let dist = i - left - 1;
                let bounded_height = height[i].min(height[left]) - height[bottom];
                water += (dist as i32) * bounded_height;
            } else {
                break;
            }
        } else {
            break;
        }
    }
    stack.push(i);
}
println!("{}", water);

This code calculates trapped rain water using a stack by iterating over the height array and computing water trapped when a taller bar is found.

Execution Table

Step	Operation	Current Index (i)	Stack Before	Stack After	Water Added	Total Water	Visual State
1	Push index 0	0	[]	[0]	0	0	[0]
2	Pop index 0 (height 0) because height[1]=1 > height[0]=0	1	[0]	[]	0	0	[]
3	Push index 1	1	[]	[1]	0	0	[1]
4	Push index 2	2	[1]	[1,2]	0	0	[1,2]
5	Pop index 2 (height 0) because height[3]=2 > height[2]=0	3	[1,2]	[1]	1	1	[1]
6	Pop index 1 (height 1) because height[3]=2 > height[1]=1	3	[1]	[]	0	1	[]
7	Push index 3	3	[]	[3]	0	1	[3]
8	Push index 4	4	[3]	[3,4]	0	1	[3,4]
9	Push index 5	5	[3,4]	[3,4,5]	0	1	[3,4,5]
10	Pop index 5 (height 0) because height[6]=1 > height[5]=0	6	[3,4,5]	[3,4]	1	2	[3,4]
11	Push index 6	6	[3,4]	[3,4,6]	0	2	[3,4,6]
12	Pop index 6 (height 1) because height[7]=3 > height[6]=1	7	[3,4,6]	[3,4]	0	2	[3,4]
13	Pop index 4 (height 1) because height[7]=3 > height[4]=1	7	[3,4]	[3]	3	5	[3]
14	Push index 7	7	[3]	[3,7]	0	5	[3,7]
15	Push index 8	8	[3,7]	[3,7,8]	0	5	[3,7,8]
16	Push index 9	9	[3,7,8]	[3,7,8,9]	0	5	[3,7,8,9]
17	Pop index 9 (height 1) because height[10]=2 > height[9]=1	10	[3,7,8,9]	[3,7,8]	1	6	[3,7,8]
18	Push index 10	10	[3,7,8]	[3,7,8,10]	0	6	[3,7,8,10]
19	Push index 11	11	[3,7,8,10]	[3,7,8,10,11]	0	6	[3,7,8,10,11]
20	End of array reached	-	[3,7,8,10,11]	[3,7,8,10,11]	0	6	[3,7,8,10,11]

💡 Reached end of height array, total trapped water is 6

Variable Tracker

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

Key Moments - 3 Insights

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

Because trapped water can only be formed when we find a right boundary taller than the bottom bar. This is shown in execution_table rows 5 and 13 where popping happens only when height[i] > height[stack top].

Why do we break the inner loop if the stack becomes empty after popping?

If the stack is empty, it means there is no left boundary to trap water. So, we cannot calculate trapped water and must stop popping. This is seen in execution_table rows 2 and 6 where after popping, stack is empty, we break.

How is the trapped water calculated using distance and bounded height?

Distance is the horizontal gap between current index and new stack top minus one. Bounded height is the minimum height of current and left bar minus bottom bar height. Multiplying these gives trapped water volume, as shown in execution_table rows 5 and 13.

Visual Quiz - 3 Questions

Look at the execution_table at step 13, how much water is added and what is the total water after this step?

A Water added: 1, Total water: 2

B Water added: 3, Total water: 5

C Water added: 0, Total water: 2

D Water added: 1, Total water: 6

💡 Hint

Check the 'Water Added' and 'Total Water' columns at step 13 in execution_table.

At which step does the stack first pop an index due to a taller bar found?

A Step 5

B Step 3

C Step 11

D Step 20

💡 Hint

Look for the first step where 'Pop' operation occurs in execution_table.

If the height at index 7 was lower, how would the total trapped water change by step 15?

A It would increase because more water can be trapped

B It would stay the same because index 7 does not affect water

C It would decrease because less water can be trapped

D It would become zero because no water can be trapped

💡 Hint

Refer to variable_tracker and execution_table steps 13-15 where index 7 height affects trapped water.

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
- Add trapped water to total
- Push current index to stack
- Continue until end
- Return total trapped water

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. When the current height is greater than the height at the top of the stack, we pop the stack to find the bottom bar and calculate trapped water between the current bar and the new top of the stack. We add this water to the total. If the stack becomes empty after popping, we stop popping because no left boundary exists. We push the current index to the stack and continue until we reach the end of the array. The total trapped water is then returned. The execution table tracks each step, stack state, water added, and total water. The variable tracker shows how stack, water, and index change over time. Key moments clarify why popping happens only when current height is greater and how trapped water is calculated. The visual quiz tests understanding of these steps.

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