Trapping Rain Water Problem in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of trapping rain water calculation

What is the output of the following Rust code that calculates trapped rain water for the given height array?

DSA Rust

fn trap(height: Vec<i32>) -> i32 {
    let n = height.len();
    let mut left_max = vec![0; n];
    let mut right_max = vec![0; n];
    let mut water = 0;

    if n == 0 {
        return 0;
    }

    left_max[0] = height[0];
    for i in 1..n {
        left_max[i] = left_max[i - 1].max(height[i]);
    }

    right_max[n - 1] = height[n - 1];
    for i in (0..n - 1).rev() {
        right_max[i] = right_max[i + 1].max(height[i]);
    }

    for i in 0..n {
        water += left_max[i].min(right_max[i]) - height[i];
    }

    water
}

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

A 6

B 5

C 7

D 8

💡 Hint

Think about how the left_max and right_max arrays help find trapped water at each position.

The code calculates the trapped water by finding the maximum height to the left and right of each bar, then sums the minimum of these two maxima minus the current height. For the given input, the total trapped water is 6 units.

🧠 Conceptual

intermediate

Understanding the role of left_max and right_max arrays

In the trapping rain water problem, what do the left_max and right_max arrays represent?

A left_max[i] is the lowest bar from the start to i; right_max[i] is the lowest bar from i to the end

B left_max[i] is the highest bar from the start to i; right_max[i] is the highest bar from i to the end

C left_max[i] and right_max[i] store the water trapped at position i

D left_max[i] and right_max[i] store the height of the bar at position i

💡 Hint

Think about how to find the boundaries that trap water at each position.

left_max[i] stores the tallest bar from the left up to i, and right_max[i] stores the tallest bar from the right up to i. These help determine the water trapped at position i.

🔧 Debug

advanced

Identify the error in this Rust code for trapping rain water

What error will this Rust code produce when run?

DSA Rust

fn trap(height: Vec<i32>) -> i32 {
    let n = height.len();
    let mut left_max = vec![0; n];
    let mut right_max = vec![0; n];
    let mut water = 0;

    if n == 0 {
        return 0;
    }

    left_max[0] = height[0];
    for i in 1..n {
        left_max[i] = left_max[i - 1].max(height[i]);
    }

    right_max[n - 1] = height[n - 1];
    for i in (0..n - 1).rev() {
        right_max[i] = right_max[i + 1].max(height[i]);
    }

    for i in 0..n {
        water += left_max[i].min(right_max[i]) - height[i];
    }

    water
}

fn main() {
    let height = vec![4,2,0,3,2,5];
    println!("{}", trap(height));
}

A No error, outputs 9

B Compilation error due to missing semicolon

C Logic error causing incorrect trapped water calculation

D Index out of bounds panic at line right_max[n] = height[n - 1];

💡 Hint

Check array indexing carefully, especially at boundaries.

The code tries to assign right_max[n], but valid indices are 0 to n-1. This causes an index out of bounds panic at runtime.

🚀 Application

advanced

Calculate trapped water for a custom height array

Given the height array [3, 0, 2, 0, 4], what is the total trapped rain water?

A 7

B 6

C 5

D 4

💡 Hint

Visualize the bars and the water trapped between them.

The trapped water units are 3 at position 1, 1 at position 2, and 3 at position 3, totaling 7.

🧠 Conceptual

expert

Time complexity of the trapping rain water algorithm using left_max and right_max arrays

What is the time complexity of the trapping rain water solution that uses left_max and right_max arrays?

A O(log n) because it uses binary search to find boundaries

B O(n^2) because it uses nested loops to calculate trapped water

C O(n) because it traverses the height array a fixed number of times

D O(1) because it uses constant extra space

💡 Hint

Consider how many times the array is traversed.

The algorithm makes three passes over the array: one to build left_max, one for right_max, and one to calculate trapped water, all linear time.

Practice

1. What does the Trapping Rain Water problem ask you to find given an array of heights?

easy

A. The total amount of water that can be trapped between the bars after raining

B. The highest bar in the array

C. The number of bars taller than a given height

D. The sum of all bar heights

Solution

1. Step 1: Understand the problem context

   The problem involves an array representing heights of bars where water can be trapped between them.

2. Step 2: Identify what is asked

   We need to find how much water can be trapped after raining, which depends on the heights and gaps between bars.

3. Final Answer:

   The total amount of water that can be trapped between the bars after raining -> Option A

4. Quick Check:

   Trapping Rain Water = Total trapped water [OK]

Hint: Think of bars as walls holding water in between [OK]

Common Mistakes:

• Confusing trapped water with total height sum
• Ignoring gaps between bars
• Only finding tallest bar instead of trapped water

2. Which Rust code snippet correctly initializes a vector of bar heights for the Trapping Rain Water problem?

easy

A. let heights = [0,1,0,2,1,0,1,3,2,1,2,1];

B. let heights = vec![0,1,0,2,1,0,1,3,2,1,2,1];

C. let heights = (0,1,0,2,1,0,1,3,2,1,2,1);

D. let heights = {0,1,0,2,1,0,1,3,2,1,2,1};

Solution

1. Step 1: Identify Rust vector syntax

   In Rust, vectors are created using vec![elements], which is dynamic and growable.

2. Step 2: Check each option

   let heights = vec![0,1,0,2,1,0,1,3,2,1,2,1]; uses vec! macro correctly; B is an array, C is a tuple, D is invalid syntax.

3. Final Answer:

   let heights = vec![0,1,0,2,1,0,1,3,2,1,2,1]; -> Option B

4. Quick Check:

   vec! macro creates vector [OK]

Hint: Use vec![] to create vectors in Rust [OK]

Common Mistakes:

• Using array syntax instead of vector
• Using tuple parentheses instead of brackets
• Using curly braces which are invalid here

3. What is the output of this Rust code snippet that calculates trapped water?

fn trap(height: Vec<i32>) -> i32 {
    let mut left = 0;
    let mut right = height.len() - 1;
    let mut left_max = 0;
    let mut right_max = 0;
    let mut water = 0;
    while left < right {
        if height[left] < height[right] {
            if height[left] > left_max {
                left_max = height[left];
            } else {
                water += left_max - height[left];
            }
            left += 1;
        } else {
            if height[right] > right_max {
                right_max = height[right];
            } else {
                water += right_max - height[right];
            }
            right -= 1;
        }
    }
    water
}

fn main() {
    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 two-pointer approach in code

   The code uses two pointers from left and right, tracking max heights and accumulating trapped water.

2. Step 2: Trace the example input

   For input [0,1,0,2,1,0,1,3,2,1,2,1], the trapped water calculated is 6 units.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Two-pointer trap water = 6 [OK]

Hint: Use two pointers and track max heights from both ends [OK]

Common Mistakes:

• Miscounting trapped water units
• Confusing left_max and right_max updates
• Off-by-one errors in pointer movement

4. Identify the bug in this Rust function for trapping rain water:

fn trap(height: Vec<i32>) -> i32 {
    let mut left = 0;
    let mut right = height.len();
    let mut left_max = 0;
    let mut right_max = 0;
    let mut water = 0;
    while left < right {
        if height[left] < height[right] {
            if height[left] > left_max {
                left_max = height[left];
            } else {
                water += left_max - height[left];
            }
            left += 1;
        } else {
            if height[right] > right_max {
                right_max = height[right];
            } else {
                water += right_max - height[right];
            }
            right -= 1;
        }
    }
    water
}

medium

A. water should be a float instead of i32

B. left_max and right_max should start at 1

C. The while loop condition should be left <= right

D. right should be initialized to height.len() - 1

Solution

1. Step 1: Check initialization of right pointer

   right is set to height.len(), which is out of bounds for indexing (max index is len()-1).

2. Step 2: Correct right initialization

   right should be height.len() - 1 to point to the last valid index.

3. Final Answer:

   right should be initialized to height.len() - 1 -> Option D

4. Quick Check:

   Indexing error fixed by right = len()-1 [OK]

Hint: Array indices go from 0 to len-1, not len [OK]

Common Mistakes:

• Using len() as index causes runtime panic
• Changing loop condition incorrectly
• Starting max heights at wrong values

5. Given the heights array [4,2,0,3,2,5], what is the total trapped rain water using the two-pointer approach?

hard

A. 6

B. 7

C. 9

D. 8

Solution

1. Step 1: Analyze heights and max boundaries

   Left max starts at 4, right max at 5. Water trapped depends on min(left_max, right_max) minus current height.

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

   Positions: - index 1: min(4,5)=4, height=2, trapped=2 - index 2: min(4,5)=4, height=0, trapped=4 - index 3: min(4,5)=4, height=3, trapped=1 - index 4: min(4,5)=4, height=2, trapped=2 Total trapped water = 2+4+1+2 = 9 units. Verified with two-pointer simulation.

3. Final Answer:

   9 -> Option C

4. Quick Check:

   Two-pointer trap water for [4,2,0,3,2,5] = 9 [OK]

Hint: Calculate trapped water by min(left_max, right_max) - height [OK]

Common Mistakes:

• Adding trapped water incorrectly at edges
• Confusing left_max and right_max updates
• Forgetting to move pointers properly