Trapping Rain Water Problem in DSA Rust - Deep Dive

Overview - Trapping Rain Water Problem

What is it?

The Trapping Rain Water Problem asks how much water can be trapped between bars of different heights after it rains. Imagine each bar as a wall, and water fills the spaces between them. The goal is to find the total amount of water that stays trapped without spilling. This problem helps us understand how to work with arrays and calculate areas efficiently.

Why it matters

Without this concept, we would struggle to solve real-world problems like calculating water storage, flood simulation, or even designing drainage systems. It teaches us how to think about boundaries and space in a simple yet powerful way. Knowing this helps in optimizing solutions where space and limits matter, saving time and resources.

Where it fits

Before this, learners should understand arrays and basic loops. After this, they can explore dynamic programming and two-pointer techniques. This problem is a stepping stone to mastering space optimization and complex array manipulations.

Mental Model

Core Idea

Water trapped above a bar depends on the tallest bars to its left and right, and the trapped water is the minimum of these heights minus the bar's own height.

Think of it like...

Imagine a row of buildings with different heights after a rainstorm. Water collects in the valleys between taller buildings, but only up to the height of the shortest building on either side. The trapped water is like puddles formed in these valleys.

Index:  0   1   2   3   4   5   6
Height: 3 | 0 | 2 | 0 | 4 | 0 | 1

Water trapped:
  At index 1: min(3,4) - 0 = 3 units
  At index 3: min(3,4) - 0 = 3 units
  At index 5: min(4,1) - 0 = 1 unit

Diagram:
  4 |       █       
  3 | █     █ █     
  2 | █   █ █ █     
  1 | █ █ █ █ █ █ █ 
     ----------------
     0 1 2 3 4 5 6

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem and how bars and water relate in a simple array.

We have an array where each number represents the height of a bar. Water can be trapped between bars if there are taller bars on both sides. For example, if the array is [3,0,2], water can fill above the 0 up to height 2 (the smaller of 3 and 2).

Result

You see that water fills the gaps between taller bars, and the amount depends on the heights around each bar.

Understanding the problem visually helps you see why water only stays where it is bounded by taller bars.

2

Foundation

Basic Array Traversal and Height Comparison

Concept: Learn to check heights on left and right sides for each bar.

For each bar, look to the left to find the tallest bar so far, and look to the right to find the tallest bar on that side. These two values determine how much water can be trapped above the current bar.

Result

You can calculate trapped water at each position by min(left_max, right_max) - current_height.

Knowing how to find max heights on both sides is key to calculating trapped water correctly.

3

Intermediate

Precomputing Left and Right Max Arrays

🤔Before reading on: do you think computing max heights on the fly or precomputing arrays is faster? Commit to your answer.

Concept: Use extra arrays to store the tallest bar to the left and right of each position to avoid repeated work.

Create two arrays: left_max and right_max. left_max[i] stores the tallest bar from the start up to i. right_max[i] stores the tallest bar from the end up to i. Then, for each bar, trapped water = min(left_max[i], right_max[i]) - height[i].

Result

This method calculates trapped water in O(n) time with O(n) extra space.

Precomputing saves time by avoiding repeated scanning, showing a classic space-time tradeoff.

4

Intermediate

Two-Pointer Technique for Space Optimization

🤔Before reading on: do you think we can solve this without extra arrays? Commit to yes or no.

Concept: Use two pointers moving inward from both ends to calculate trapped water using constant space.

Initialize two pointers at the start and end of the array. Keep track of left_max and right_max as you move pointers inward. At each step, move the pointer with the smaller height, calculate trapped water if possible, and update max heights.

Result

This approach uses O(1) extra space and still runs in O(n) time.

Two-pointer method cleverly uses the problem's constraints to reduce space without losing efficiency.

5

Advanced

Implementing the Two-Pointer Solution in Rust

🤔Before reading on: do you think Rust's ownership and mutability rules affect pointer manipulation? Commit to yes or no.

Concept: Write clean, safe Rust code using mutable variables and loops to implement the two-pointer algorithm.

```rust fn trap(height: Vec) -> 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 bars = vec![3, 0, 2, 0, 4]; println!("{}", trap(bars)); } ```

Result

Output: 7 Explanation: The total trapped water units are 7 for the input [3,0,2,0,4].

Implementing in Rust shows how ownership and mutability guide safe pointer updates in algorithms.

6

Expert

Analyzing Edge Cases and Performance Limits

🤔Before reading on: do you think the algorithm handles empty or uniform height arrays correctly? Commit to yes or no.

Concept: Explore how the algorithm behaves with special inputs and its time and space complexity.

Edge cases include empty arrays, arrays with all bars of the same height, or strictly increasing/decreasing heights. The algorithm returns zero trapped water in these cases. Time complexity is O(n) because each pointer moves once. Space complexity is O(1) for the two-pointer method.

Result

The algorithm is robust and efficient across all valid inputs.

Understanding edge cases prevents bugs and confirms the algorithm's reliability in production.

Under the Hood

The algorithm works by maintaining two pointers and tracking the maximum heights seen so far from both ends. At each step, it moves the pointer with the smaller height inward, because trapped water depends on the smaller boundary. It calculates trapped water by subtracting the current bar's height from the known maximum boundary on that side. This ensures all trapped water is counted exactly once.

Why designed this way?

This design avoids repeated scanning of the array for max heights, reducing time complexity from O(n^2) to O(n). The two-pointer approach balances space and time efficiency, making it practical for large inputs. Earlier methods used extra arrays, but this method was created to optimize memory use without sacrificing speed.

┌─────────────┐
│ Start       │
│ left=0      │
│ right=n-1   │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ Compare     │
│ height[left]│
│ and height[right]│
└─────┬───────┘
      │
 ┌────┴─────┐
 │          │
 ▼          ▼
Move left  Move right
pointer    pointer
│          │
Update    Update
left_max  right_max
│          │
Calculate trapped water if
current height < max
│          │
Repeat until left >= right

Myth Busters - 3 Common Misconceptions

Quick: Does the trapped water at a bar depend only on the tallest bar to its left? Commit to yes or no.

Common Belief: Trapped water depends only on the tallest bar to the left of the current bar.

Reality: Trapped water depends on the minimum of the tallest bars on both left and right sides.

Why it matters: Ignoring the right side can cause overestimating trapped water, leading to wrong answers.

Quick: Can we calculate trapped water by summing all positive differences between adjacent bars? Commit to yes or no.

Common Belief: Summing positive height differences between adjacent bars gives total trapped water.

Reality: This method misses water trapped over multiple bars and valleys; it only accounts for local differences.

Why it matters: Using this incorrect method underestimates trapped water, failing in complex cases.

Quick: Is it always better to use extra arrays for left and right max heights? Commit to yes or no.

Common Belief: Using extra arrays for max heights is always the best approach.

Reality: While easier to implement, extra arrays use more memory; the two-pointer method is more space-efficient.

Why it matters: Choosing the wrong method can waste memory and reduce performance in large-scale problems.

Expert Zone

1

The two-pointer method relies on the insight that the smaller boundary determines trapped water, allowing pointer movement without missing cases.

2

In Rust, careful handling of indices and mutability ensures safe and efficient pointer updates without runtime errors.

3

Edge cases like flat or strictly monotonic arrays confirm the algorithm's correctness and help optimize early exits.

When NOT to use

This approach is not suitable if the input is streaming or too large to fit in memory, where online or approximate algorithms might be better. Also, if you need to find trapped water at specific positions repeatedly, precomputing arrays might be more efficient.

Production Patterns

In real systems, this problem appears in terrain modeling, urban planning for drainage, and game development for realistic water simulation. Professionals use optimized two-pointer solutions for fast calculations and combine them with visualization tools.

Connections

Two-Pointer Technique

Builds-on

Understanding the two-pointer technique here helps solve many array problems involving pairs or boundaries efficiently.

Dynamic Programming

Related pattern

Precomputing left and right max arrays is a form of dynamic programming, storing intermediate results to avoid repeated work.

Hydrology and Civil Engineering

Application domain

The problem models real-world water trapping and drainage, linking algorithmic thinking to physical water flow and storage.

Common Pitfalls

#1 Calculating trapped water using only one side's max height.

Wrong approach:

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

Correct approach:

for i in 0..height.len() {
water += std::cmp::min(left_max[i], right_max[i]) - height[i];
}

Root cause:

Misunderstanding that water is limited by both sides, not just one.

#2 Using nested loops to find max heights for each bar, causing slow performance.

Wrong approach:

for i in 0..height.len() {
let left_max = height[0..=i].iter().max().unwrap();
let right_max = height[i..].iter().max().unwrap();
water += std::cmp::min(*left_max, *right_max) - height[i];
}

Correct approach:

Precompute left_max and right_max arrays once, then calculate trapped water in a single loop.

Root cause:

Not optimizing repeated max calculations, leading to O(n^2) time.

#3 Incorrect pointer movement in two-pointer method causing infinite loop or wrong result.

Wrong approach:

while left <= right {
if height[left] > height[right] {
left += 1;
} else {
right -= 1;
}
}

Correct approach:

while left < right {
if height[left] < height[right] {
// process left
left += 1;
} else {
// process right
right -= 1;
}
}

Root cause:

Misunderstanding the condition for pointer movement and loop termination.

Key Takeaways

Trapped water at each bar depends on the minimum of the tallest bars on its left and right sides minus its own height.

Precomputing max heights or using two pointers are efficient ways to solve the problem in linear time.

The two-pointer method optimizes space by moving inward from both ends, updating max heights dynamically.

Edge cases like empty or uniform height arrays result in zero trapped water and confirm algorithm robustness.

Understanding this problem builds skills in array manipulation, boundary conditions, and space-time tradeoffs.

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