Trapping Rain Water Problem in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of trapping rain water calculation

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

DSA C++

int trap(std::vector<int>& height) {
    int n = height.size();
    int left = 0, right = n - 1;
    int left_max = 0, right_max = 0;
    int 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--;
        }
    }
    return water;
}

int main() {
    std::vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
    std::cout << trap(height);
    return 0;
}

A 6

B 5

C 7

D 8

💡 Hint

Use two pointers and track the maximum heights from both ends to calculate trapped water.

The code uses two pointers from left and right ends, updating left_max and right_max. Water trapped is the sum of differences between max heights and current heights where applicable. For the given array, total trapped water is 6 units.

🧠 Conceptual

intermediate

Understanding the trapping rain water problem

Which of the following best describes the main idea behind the trapping rain water problem?

A Calculate the total water trapped by finding the minimum of maximum heights on both sides for each position.

B Sum all heights and subtract the minimum height to find trapped water.

C Count the number of bars taller than the average height to estimate trapped water.

D Find the maximum height and multiply by the number of bars to get trapped water.

💡 Hint

Think about how water is trapped between taller bars on both sides.

Water trapped at each position depends on the shorter of the tallest bars to the left and right minus the height at that position.

🔧 Debug

advanced

Identify the error in the trapping rain water code

What error will the following C++ code produce when run?

DSA C++

int trap(std::vector<int>& height) {
    int n = height.size();
    int left = 0, right = n - 1;
    int left_max = 0, right_max = 0;
    int 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--;
        }
    }
    return water;
}

int main() {
    std::vector<int> height = {4,2,0,3,2,5};
    std::cout << trap(height);
    return 0;
}

A Runtime error due to out-of-bounds access

B No error, outputs 9

C Infinite loop

D Compilation error

💡 Hint

Check the loop condition and pointer updates carefully.

There is no error in the code. The loop condition left <= right does not cause an infinite loop because when left == right, the else branch is executed (since height[left] == height[right]), updating right_max and decrementing right, causing left > right and the loop to exit. The code correctly outputs 9.

🚀 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 5

B 6

C 7

D 4

💡 Hint

Visualize the bars and count water units between them.

Water trapped: at index 1: min(3,4) - 0 = 3, at index 2: min(3,4) - 2 = 1, at index 3: min(3,4) - 0 = 3, totaling 7 units.

❓ Predict Output

expert

Output of optimized trapping rain water code with prefix and suffix arrays

What is the output of the following C++ code that uses prefix and suffix arrays to calculate trapped rain water?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int trap(std::vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;
    std::vector<int> left_max(n), right_max(n);
    left_max[0] = height[0];
    for (int i = 1; i < n; i++) {
        left_max[i] = std::max(left_max[i-1], height[i]);
    }
    right_max[n-1] = height[n-1];
    for (int i = n-2; i >= 0; i--) {
        right_max[i] = std::max(right_max[i+1], height[i]);
    }
    int water = 0;
    for (int i = 0; i < n; i++) {
        water += std::min(left_max[i], right_max[i]) - height[i];
    }
    return water;
}

int main() {
    std::vector<int> height = {4,2,0,3,2,5};
    std::cout << trap(height);
    return 0;
}

A 7

B 10

C 8

D 9

💡 Hint

Use prefix and suffix max arrays to find trapped water at each position.

The prefix and suffix arrays store max heights from left and right. The trapped water is sum of min(left_max, right_max) - height at each index. For the input, total trapped water is 9.

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