Trapping Rain Water Problem in DSA C++ - Execution Trace

Concept Flow - Trapping Rain Water Problem

Start with height array

↓

Find max height to left for each bar

↓

Find max height to right for each bar

↓

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

↓

Sum all trapped water

↓

Return total trapped water

The flow shows how for each bar, we find the tallest bar on the left and right, then calculate trapped water by the difference between the smaller max and current height.

Execution Sample

DSA C++

int trap(vector<int>& height) {
  int n = height.size();
  vector<int> left_max(n), right_max(n);
  int water = 0;
  // compute left_max
  // compute right_max
  // calculate trapped water
  return water;
}

This code calculates trapped rain water by precomputing max heights on left and right, then summing trapped water at each position.

Execution Table

Step	Operation	Index	Left Max Array	Right Max Array	Water Trapped at Index	Total Water	Visual State
1	Initialize left_max[0]	0	[0, _, _, _, _, _]	[_, _, _, _, _, _]	0	0	Height: [0,1,0,2,1,0]
2	Compute left_max[1]	1	[0,1,_,_,_,_]	[_, _, _, _, _, _]	0	0	Height: [0,1,0,2,1,0]
3	Compute left_max[2]	2	[0,1,1,_,_,_]	[_, _, _, _, _, _]	0	0	Height: [0,1,0,2,1,0]
4	Compute left_max[3]	3	[0,1,1,2,_,_]	[_, _, _, _, _, _]	0	0	Height: [0,1,0,2,1,0]
5	Compute left_max[4]	4	[0,1,1,2,2,_]	[_, _, _, _, _, _]	0	0	Height: [0,1,0,2,1,0]
6	Compute left_max[5]	5	[0,1,1,2,2,2]	[_, _, _, _, _, _]	0	0	Height: [0,1,0,2,1,0]
7	Initialize right_max[5]	5	[0,1,1,2,2,2]	[_, _, _, _, _, 0]	0	0	Height: [0,1,0,2,1,0]
8	Compute right_max[4]	4	[0,1,1,2,2,2]	[_, _, _, _, 1, 0]	0	0	Height: [0,1,0,2,1,0]
9	Compute right_max[3]	3	[0,1,1,2,2,2]	[_, _, _, 2, 1, 0]	0	0	Height: [0,1,0,2,1,0]
10	Compute right_max[2]	2	[0,1,1,2,2,2]	[_, _, 2, 2, 1, 0]	0	0	Height: [0,1,0,2,1,0]
11	Compute right_max[1]	1	[0,1,1,2,2,2]	[_, 2, 2, 2, 1, 0]	0	0	Height: [0,1,0,2,1,0]
12	Compute right_max[0]	0	[0,1,1,2,2,2]	[2, 2, 2, 2, 1, 0]	0	0	Height: [0,1,0,2,1,0]
13	Calculate water trapped at index 0	0	[0,1,1,2,2,2]	[2,2,2,2,1,0]	min(0,2)-0=0	0	Water trapped: 0
14	Calculate water trapped at index 1	1	[0,1,1,2,2,2]	[2,2,2,2,1,0]	min(1,2)-1=0	0	Water trapped: 0
15	Calculate water trapped at index 2	2	[0,1,1,2,2,2]	[2,2,2,2,1,0]	min(1,2)-0=1	1	Water trapped: 1
16	Calculate water trapped at index 3	3	[0,1,1,2,2,2]	[2,2,2,2,1,0]	min(2,2)-2=0	1	Water trapped: 1
17	Calculate water trapped at index 4	4	[0,1,1,2,2,2]	[2,2,2,2,1,0]	min(2,1)-1=0	1	Water trapped: 1
18	Calculate water trapped at index 5	5	[0,1,1,2,2,2]	[2,2,2,2,1,0]	min(2,0)-0=0	1	Water trapped: 1
19	Return total trapped water	-	[0,1,1,2,2,2]	[2,2,2,2,1,0]	-	1	Final trapped water = 1

💡 All indices processed, total trapped water calculated

Variable Tracker

Variable	Start	After Step 6	After Step 12	After Step 18	Final
left_max	[]	[0,1,1,2,2,2]	[0,1,1,2,2,2]	[0,1,1,2,2,2]	[0,1,1,2,2,2]
right_max	[]	[]	[2,2,2,2,1,0]	[2,2,2,2,1,0]	[2,2,2,2,1,0]
water	0	0	0	1	1

Key Moments - 3 Insights

Why do we take the minimum of left_max and right_max when calculating trapped water?

Because water can only be trapped up to the height of the shorter boundary. See execution_table rows 13-18 where min(left_max, right_max) is used.

Why is water trapped zero or positive, never negative?

If min(left_max, right_max) <= height, no water is trapped, so we take zero (using max(0, min(left_max, right_max) - height)). See step 17 where min(2,1)-1=0.

Why do we precompute left_max and right_max arrays?

To efficiently find the tallest bar on each side for every index without repeated scanning. This is shown in steps 2-6 and 7-12.

Visual Quiz - 3 Questions

Look at the execution_table at step 15, what is the water trapped at index 2?

A 0

B 1

C 2

D -1

💡 Hint

Check the 'Water Trapped at Index' column at step 15 in execution_table.

At which step is the right_max array fully computed?

A Step 6

B Step 12

C Step 18

D Step 1

💡 Hint

Look at the 'Right Max Array' column and find when it has no underscores.

If the height at index 4 changed from 1 to 3, how would the total trapped water change at step 18?

A Increase

B Decrease

C Remain the same

D Become negative

💡 Hint

Consider how trapped water depends on height and boundaries in variable_tracker and execution_table.

Concept Snapshot

Trapping Rain Water Problem:
- For each bar, find max height to left and right.
- Water trapped = min(left_max, right_max) - height.
- Sum all trapped water for total.
- Use arrays to store left_max and right_max for O(n) time.
- Water trapped can't be negative; use max with 0.

Full Transcript

The Trapping Rain Water problem calculates how much water can be trapped between bars of different heights. We first find the tallest bar to the left and right of each bar. Then, for each bar, the water trapped is the smaller of these two heights minus the bar's own height. We sum these values for all bars to get the total trapped water. The process uses two arrays, left_max and right_max, to store the tallest bars seen so far from left and right sides, respectively. This avoids repeated scanning and makes the solution efficient. Negative trapped water values are treated as zero because water cannot be negative. The final result is the sum of all positive trapped water amounts.

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 gives an array representing heights of bars and asks how much water can be trapped between them after it rains.

2. Step 2: Identify the goal

   The goal is to calculate the total trapped water volume, not just heights or counts.

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 gaps [OK]

Common Mistakes:

• Confusing trapped water with highest bar height
• Summing bar heights instead of trapped water
• Counting bars taller than a certain height

2. Which of the following C++ code snippets correctly initializes a vector named heights with values {0,1,0,2,1,0,1,3,2,1,2,1}?

easy

A. std::vector<int> heights = (0,1,0,2,1,0,1,3,2,1,2,1);

B. std::vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1};

C. vector<int> heights(0,1,0,2,1,0,1,3,2,1,2,1);

D. std::vector heights = {0,1,0,2,1,0,1,3,2,1,2,1};

Solution

1. Step 1: Check vector initialization syntax

   In C++, std::vector<int> can be initialized with curly braces and values inside, like {0,1,...}.

2. Step 2: Identify correct syntax

   std::vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1}; uses correct syntax with std::vector<int> and brace initialization.

3. Final Answer:

   std::vector<int> heights = {0,1,0,2,1,0,1,3,2,1,2,1}; -> Option B

4. Quick Check:

   Correct vector init uses braces and type [OK]

Hint: Use curly braces {} for vector initialization [OK]

Common Mistakes:

• Omitting std:: before vector
• Using parentheses instead of braces
• Not specifying vector type

3. What is the output of the following C++ code snippet that calculates trapped rain water?

std::vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = height.size();
int left_max = 0, right_max = 0, left = 0, right = n - 1, 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++;
  } else {
    if (height[right] >= right_max) right_max = height[right];
    else water += right_max - height[right];
    right--;
  }
}
std::cout << water << std::endl;

medium

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Understand two-pointer approach

   Two pointers move inward, tracking max heights on left and right, accumulating trapped water where current height is less than max.

2. Step 2: Trace the code logic on given input

   For input {0,1,0,2,1,0,1,3,2,1,2,1}, the total trapped water calculated is 6 units.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Two-pointer trapped water = 6 [OK]

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

Common Mistakes:

• Not updating left_max or right_max correctly
• Adding negative water amounts
• Confusing left and right pointer moves

4. Identify the bug in this C++ code snippet for trapping rain water and select the fix:

std::vector<int> height = {4,2,0,3,2,5};
int n = height.size();
int left_max = 0, right_max = 0, left = 0, right = n - 1, 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++;
  } else {
    if (height[right] > right_max) right_max = height[right];
    else water += right_max - height[right];
    right--;
  }
}
std::cout << water << std::endl;

medium

A. Initialize left_max and right_max to height[0] and height[n-1] respectively

B. Use '>=' instead of '>' when updating left_max and right_max

C. Change while condition to 'left < right' to avoid double counting

D. No bug, code is correct

Solution

1. Step 1: Analyze loop condition impact

   The loop uses 'left <= right', which causes the middle element to be processed twice, leading to incorrect water calculation.

2. Step 2: Fix loop condition

   Changing condition to 'left < right' ensures each element is processed once, preventing double counting.

3. Final Answer:

   Change while condition to 'left < right' to avoid double counting -> Option C

4. Quick Check:

   Loop condition 'left < right' fixes double count bug [OK]

Hint: Use strict less than in two-pointer loops [OK]

Common Mistakes:

• Using <= instead of < in while loop
• Not updating max heights correctly
• Assuming no bug without testing

5. Given an array representing heights of bars, how would you modify the standard trapping rain water algorithm to handle very large input efficiently without extra space?

hard

A. Use recursion to calculate trapped water for each bar

B. Precompute left_max and right_max arrays and sum trapped water using extra arrays

C. Sort the array and calculate trapped water based on sorted positions

D. Use two pointers from both ends, track max heights, and calculate trapped water on the fly

Solution

1. Step 1: Understand space constraints

   Precomputing arrays uses extra space O(n), which is costly for very large inputs.

2. Step 2: Use two-pointer approach for O(1) space

   Two pointers from both ends track max heights and calculate trapped water without extra arrays, making it efficient.

3. Final Answer:

   Use two pointers from both ends, track max heights, and calculate trapped water on the fly -> Option D

4. Quick Check:

   Two-pointer approach = efficient O(1) space [OK]

Hint: Two pointers save space by avoiding extra arrays [OK]

Common Mistakes:

• Using extra arrays causing high memory use
• Sorting changes bar order, invalid for trapping water
• Recursion adds overhead and complexity