Trapping Rain Water Problem in DSA Rust - Execution Trace

Concept Flow - Trapping Rain Water Problem

Start with height array

↓

Initialize left, right pointers

↓

Compare height[left

↓

Move left pointer

↓

Calculate trapped water at pointer

↓

Add trapped water to total

↓

Repeat until left >= right

↓

Return total trapped water

We use two pointers from both ends, move inward comparing heights, calculating trapped water at each step until pointers meet.

Execution Sample

DSA Rust

let height = vec![0,1,0,2,1,0,1,3,2,1,2,1];
let mut left = 0;
let mut right = height.len() - 1;
let mut left_max = 0;
let mut right_max = 0;
let mut water = 0;

Initialize pointers and variables to track max heights and trapped water.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Left Max	Right Max	Water Added	Total Water	Visual State
1	Initialize pointers and max heights	0	11	0	0	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
2	Compare height[left]=0 and height[right]=1; left < right	0	11	0	1	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
3	height[left]=0 < height[right]=1; move left	1	11	1	1	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
4	height[left]=1 >= left_max=0; update left_max=1	1	11	1	1	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
5	Move left to 2; height[left]=0 < left_max=1; water trapped=1	2	11	1	1	1	1	[0,1,0,2,1,0,1,3,2,1,2,1]
6	Move left to 3; height[left]=2 >= left_max=1; update left_max=2	3	11	2	1	0	1	[0,1,0,2,1,0,1,3,2,1,2,1]
7	Compare height[left]=2 and height[right]=1; left >= right? No	3	11	2	1	0	1	[0,1,0,2,1,0,1,3,2,1,2,1]
8	height[left]=2 >= height[right]=1; move right	3	10	2	2	0	1	[0,1,0,2,1,0,1,3,2,1,2,1]
9	height[right]=2 >= right_max=1; update right_max=2	3	10	2	2	0	1	[0,1,0,2,1,0,1,3,2,1,2,1]
10	Move right to 9; height[right]=1 < right_max=2; water trapped=1	3	9	2	2	1	2	[0,1,0,2,1,0,1,3,2,1,2,1]
11	Move right to 8; height[right]=2 >= right_max=2; update right_max=2	3	8	2	2	0	2	[0,1,0,2,1,0,1,3,2,1,2,1]
12	Move right to 7; height[right]=3 >= right_max=2; update right_max=3	3	7	2	3	0	2	[0,1,0,2,1,0,1,3,2,1,2,1]
13	Compare height[left]=2 and height[right]=3; left < right	3	7	2	3	0	2	[0,1,0,2,1,0,1,3,2,1,2,1]
14	height[left]=2 < height[right]=3; move left	4	7	2	3	0	2	[0,1,0,2,1,0,1,3,2,1,2,1]
15	height[left]=1 < left_max=2; water trapped=1	4	7	2	3	1	3	[0,1,0,2,1,0,1,3,2,1,2,1]
16	Move left to 5; height[left]=0 < left_max=2; water trapped=2	5	7	2	3	2	5	[0,1,0,2,1,0,1,3,2,1,2,1]
17	Move left to 6; height[left]=1 < left_max=2; water trapped=1	6	7	2	3	1	6	[0,1,0,2,1,0,1,3,2,1,2,1]
18	Move left to 7; height[left]=3 >= left_max=2; update left_max=3	7	7	3	3	0	6	[0,1,0,2,1,0,1,3,2,1,2,1]
19	left >= right; stop	7	7	3	3	0	6	[0,1,0,2,1,0,1,3,2,1,2,1]

💡 Pointers met at index 7; all trapped water calculated.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	After 13	After 14	After 15	After 16	After 17	Final
left	0	0	1	2	3	3	3	3	3	3	3	3	3	3	4	5	6	7	7
right	11	11	11	11	11	10	9	8	7	7	7	7	7	7	7	7	7	7	7
left_max	0	0	1	1	2	2	2	2	2	2	2	2	2	2	2	2	2	2	3
right_max	0	1	1	1	1	1	2	2	3	3	3	3	3	3	3	3	3	3	3
water	0	0	0	1	1	1	1	1	1	2	2	2	2	2	3	5	6	6	6

Key Moments - 3 Insights

Why do we move the pointer with the smaller height instead of both pointers?

Because trapped water depends on the smaller boundary. Moving the smaller height pointer inward allows us to find a taller boundary to trap water. See execution_table steps 2, 3, and 8 where left or right pointer moves based on comparison.

Why do we update left_max or right_max only when current height is greater?

Because left_max and right_max track the highest boundary seen so far from each side. We update them only when we find a taller bar to correctly calculate trapped water. See execution_table steps 4, 6, 9, 11, 12, and 18.

How is trapped water calculated at each step?

Trapped water at a pointer is max(0, max_height - current_height). We add this only when current height is less than max height. See execution_table steps 5, 10, 15, 16, and 17.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the water added and total water?

A Water Added = 1, Total Water = 1

B Water Added = 0, Total Water = 0

C Water Added = 2, Total Water = 2

D Water Added = 1, Total Water = 0

💡 Hint

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

At which step do left and right pointers meet, stopping the process?

A Step 18

B Step 19

C Step 17

D Step 20

💡 Hint

Look for the step where 'left >= right; stop' is noted in the Operation column.

If height[right] was always smaller than height[left], which pointer would move more often?

A Left pointer

B Right pointer

C Both equally

D Neither moves

💡 Hint

Refer to the concept_flow and execution_table steps where pointer movement depends on height comparison.

Concept Snapshot

Trapping Rain Water Problem:
- Use two pointers at array ends.
- Move pointer with smaller height inward.
- Track max heights from both sides.
- Calculate trapped water as max_height - current_height.
- Sum trapped water until pointers meet.

Full Transcript

The Trapping Rain Water problem is solved by using two pointers starting at the left and right ends of the height array. We keep track of the maximum height seen so far from the left and right sides. At each step, we compare the heights at the pointers. We move the pointer with the smaller height inward because the trapped water depends on the smaller boundary. When moving a pointer, if the current height is less than the max height on that side, we add the difference to the total trapped water. Otherwise, we update the max height. This process continues until the pointers meet. The total trapped water is the sum of all trapped water calculated at each step.

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