Trapping Rain Water Using Stack in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a stack to solve the Trapping Rain Water problem?

Use a stack to keep track of bars that are bounded by higher bars on both sides. When a higher bar is found, calculate trapped water by popping from the stack and using the distance and height difference.

beginner

In the stack approach, what does each element in the stack represent?

Each element represents the index of a bar in the height array, used to find boundaries and calculate trapped water.

intermediate

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

Because we found a right boundary taller than the bar at the top, so we can calculate trapped water between the left boundary (new top of stack) and this right boundary.

intermediate

What happens if the stack is empty after popping the top element during water calculation?

No left boundary exists, so no water can be trapped for that popped bar.

intermediate

How is the trapped water volume calculated between boundaries in the stack method?

Water trapped = (distance between boundaries - 1) * (min height of boundaries - height of popped bar).

What data structure is primarily used to solve the Trapping Rain Water problem efficiently?

A Stack

B Queue

C Linked List

D Hash Map

Stack helps track bars and boundaries to calculate trapped water efficiently.

When do we calculate trapped water in the stack approach?

A When current bar is shorter than top of stack

B When current bar is taller than top of stack

C When stack is empty

D At the end of the array only

Trapped water is calculated when a taller bar is found, forming a right boundary.

What does the stack store in the Trapping Rain Water problem?

A Indices of bars

B Water volumes

C Heights of bars

D Distances between bars

Stack stores indices to access heights and calculate distances.

If the stack is empty after popping, what does it mean for trapped water calculation?

A Water trapped is maximum

B Water trapped equals height of popped bar

C No water trapped for that bar

D Calculation is skipped

No left boundary means no trapped water for that popped bar.

Which formula correctly calculates trapped water volume between boundaries?

A (distance - 1) * (max height + popped height)

B (distance + 1) * (max height - popped height)

C (distance) * (popped height)

D (distance - 1) * (min height - popped height)

Water volume = (distance - 1) * (minimum boundary height - popped bar height).

Explain step-by-step how the stack is used to calculate trapped rain water.

Think about how boundaries form and how water is trapped between them.

Describe how trapped water volume is computed between two boundaries using the stack method.

Focus on the geometry of trapped water between bars.

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