Trapping Rain Water Using Stack in DSA Rust - Build from Scratch

Trapping Rain Water Using Stack

📖 Scenario: Imagine you have a row of walls of different heights. When it rains, water gets trapped between these walls. We want to find out how much water is trapped after it rains.

🎯 Goal: You will write a Rust program that uses a stack to calculate the total amount of trapped rain water given a list of wall heights.

📋 What You'll Learn

Create a vector called heights with the exact values [0,1,0,2,1,0,1,3,2,1,2,1].

Create a stack using a vector called stack to store indices of walls.

Use a while loop to process the heights and calculate trapped water using the stack.

Print the total trapped water as an integer.

💡 Why This Matters

🌍 Real World

Calculating trapped rain water helps in urban planning and drainage system design to prevent flooding.

💼 Career

Understanding stack-based algorithms and problem-solving skills are important for software engineering interviews and real-world coding tasks.

1

Create the heights vector

Create a vector called heights with these exact values: [0,1,0,2,1,0,1,3,2,1,2,1].

DSA Rust

# Create the heights vector with the given values
# Your code here

Hint

Use let heights = vec![...] to create the vector with the exact numbers.

2

Create the stack and initialize variables

Add a mutable vector called stack to store indices. Also create a mutable integer variable called water_trapped and set it to 0. Create a mutable integer variable called current and set it to 0.

DSA Rust

fn main() {
    let heights = vec![0,1,0,2,1,0,1,3,2,1,2,1];
    // Create a mutable vector called stack to store indices
    // Create mutable variables water_trapped and current set to 0
    // Your code here
}

Hint

Use let mut stack: Vec = Vec::new(); to create the stack.

Use let mut water_trapped = 0; and let mut current = 0; for counters.

3

Implement the main loop to calculate trapped water

Use a while loop with the condition current < heights.len(). Inside the loop, use another while loop to check if stack is not empty and heights[current] > heights[stack[stack.len() - 1]]. Inside this inner loop, pop the top of the stack into a variable called top. If the stack becomes empty after popping, break the inner loop. Otherwise, calculate the distance between current and the new top of the stack minus one, and calculate the bounded height as the minimum of heights[current] and heights[stack[stack.len() - 1]] minus heights[top]. Add the product of distance and bounded height to water_trapped. After the inner loop, push current onto the stack and increment current by one.

DSA Rust

fn main() {
    let heights = vec![0,1,0,2,1,0,1,3,2,1,2,1];
    let mut stack: Vec = Vec::new();
    let mut water_trapped: usize = 0;
    let mut current: usize = 0;
    // Use a while loop with condition current  heights[stack top]
    // Pop top, check if stack empty, break if yes
    // Calculate distance and bounded_height
    // Add trapped water
    // Push current to stack and increment current
    // Your code here
}

Hint

Use while current < heights.len() for the main loop.

Use while !stack.is_empty() && heights[current] > heights[*stack.last().unwrap()] for the inner loop.

Pop from stack with stack.pop().unwrap().

Calculate distance and bounded height carefully.

4

Print the total trapped water

Add a println! statement to print the value of water_trapped.

DSA Rust

fn main() {
    let heights = vec![0,1,0,2,1,0,1,3,2,1,2,1];
    let mut stack: Vec = Vec::new();
    let mut water_trapped: usize = 0;
    let mut current: usize = 0;

    while current  heights[*stack.last().unwrap()] {
            let top = stack.pop().unwrap();
            if stack.is_empty() {
                break;
            }
            let distance = current - *stack.last().unwrap() - 1;
            let bounded_height = (std::cmp::min(heights[current], heights[*stack.last().unwrap()]) - heights[top]) as usize;
            water_trapped += distance * bounded_height;
        }
        stack.push(current);
        current += 1;
    }
    // Print the total trapped water
    // Your code here
}

Hint

Use println!("{}", water_trapped); to print the result.

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