Trapping Rain Water Problem in DSA Rust

Mental Model

We want to find how much water can be trapped between bars of different heights after it rains.

Analogy: Imagine a row of buildings with different heights. When it rains, water fills the gaps between buildings but only up to the height of the shortest building on either side.

Height bars: 3 0 2 0 4
Visual: 4 |       ↑
        3 | ↑     ↑
        2 | ↑   ↑ ↑
        1 | ↑   ↑ ↑
        0 | ↑ ↑ ↑ ↑ ↑
          0 1 2 3 4  (indices)

Dry Run Walkthrough

Input: heights: [3, 0, 2, 0, 4]

Goal: Calculate total water trapped between bars after raining

Step 1: Calculate max height to the left for each bar

left_max = [3, 3, 3, 3, 4]

Why: We need to know the tallest bar on the left to know how much water can be trapped

Step 2: Calculate max height to the right for each bar

right_max = [4, 4, 4, 4, 4]

Why: We need to know the tallest bar on the right to know how much water can be trapped

Step 3: Calculate trapped water at each bar by min(left_max, right_max) - height

water trapped per bar = [0, 3, 1, 3, 0]

Why: Water level is limited by the shorter side, subtract bar height to get trapped water

Step 4: Sum trapped water from all bars

total water = 0 + 3 + 1 + 3 + 0 = 7

Why: Total trapped water is sum of water trapped at each bar

Result:

Final trapped water: 7 units

Annotated Code

DSA Rust

fn trap(height: Vec<i32>) -> i32 {
    let n = height.len();
    if n == 0 { return 0; }

    let mut left_max = vec![0; n];
    let mut right_max = vec![0; n];
    let mut water = 0;

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

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

    for i in 0..n {
        let min_height = left_max[i].min(right_max[i]);
        if min_height > height[i] {
            water += min_height - height[i]; // add trapped water at bar i
        }
    }

    water
}

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

left_max[i] = left_max[i - 1].max(height[i]); // build left max array

build array of tallest bar from left up to current index

right_max[i] = right_max[i + 1].max(height[i]); // build right max array

build array of tallest bar from right up to current index

if min_height > height[i] { water += min_height - height[i]; }

calculate trapped water at current bar by difference of min boundary and bar height

Output

7

Complexity Analysis

Time: O(n) because we traverse the height array three times: once for left max, once for right max, and once to calculate trapped water

Space: O(n) because we use two extra arrays to store left max and right max heights

vs Alternative: Compared to a naive approach that checks left and right max for each bar separately (O(n^2)), this method is much faster by precomputing max arrays

Edge Cases

empty height array

returns 0 because no bars means no trapped water

DSA Rust

if n == 0 { return 0; }

all bars same height

returns 0 because no space to trap water

DSA Rust

water += min_height - height[i]; (no addition since min_height == height[i])

strictly increasing or decreasing bars

returns 0 because water cannot be trapped on slopes

DSA Rust

water += min_height - height[i]; (no addition since min_height <= height[i])

When to Use This Pattern

When you see a problem asking how much water can be trapped between bars or heights, use the trapping rain water pattern by precomputing max heights from both sides to find water level at each position.

Common Mistakes

Mistake: Calculating trapped water by only looking at one side's max height
Fix: Always consider the minimum of left max and right max heights to find the water level

Mistake: Not handling empty input array
Fix: Add a guard clause to return 0 if the input array is empty

Summary

Calculates total water trapped between bars after raining by using max heights from left and right.

Use when you need to find trapped water volume between elevation bars or buildings.

The trapped water at each bar depends on the shorter tallest bar on either side minus the bar's own height.

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