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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of trapping rain water calculation using two-pointer approach

What is the output of the following C code that calculates trapped rain water using the two-pointer technique?

DSA C

#include <stdio.h>

int trap(int* height, int heightSize) {
    int left = 0, right = heightSize - 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() {
    int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int size = sizeof(height)/sizeof(height[0]);
    printf("%d\n", trap(height, size));
    return 0;
}

A 6

B 5

C 7

D 8

💡 Hint

Think about how the two-pointer approach accumulates water by comparing left and right heights.

The two-pointer approach calculates trapped water by moving pointers inward and accumulating water where the current height is less than the max height seen so far on that side. For the given input, the total trapped water is 6 units.

🧠 Conceptual

intermediate

Understanding the role of max height arrays in trapping rain water

In the trapping rain water problem, why do we precompute arrays of maximum heights to the left and right of each position?

A To know the highest wall on both sides to calculate trapped water at each position

B To sort the heights for easier calculation

C To find the minimum height in the array

D To count the number of walls taller than current position

💡 Hint

Think about how trapped water depends on the tallest walls around a position.

Trapped water at a position depends on the minimum of the tallest walls to the left and right minus the height at that position. Precomputing max heights arrays helps find these values efficiently.

🔧 Debug

advanced

Identify the error in this trapping rain water implementation

What error does the following C code produce when run?

DSA C

#include <stdio.h>

int trap(int* height, int heightSize) {
    int left_max[heightSize];
    int right_max[heightSize];
    int water = 0;
    left_max[0] = height[0];
    for (int i = 1; i < heightSize; i++) {
        left_max[i] = (height[i] > left_max[i-1]) ? height[i] : left_max[i-1];
    }
    right_max[heightSize] = height[heightSize-1];
    for (int i = heightSize - 2; i >= 0; i--) {
        right_max[i] = (height[i] > right_max[i+1]) ? height[i] : right_max[i+1];
    }
    for (int i = 0; i < heightSize; i++) {
        water += (left_max[i] < right_max[i] ? left_max[i] : right_max[i]) - height[i];
    }
    return water;
}

int main() {
    int height[] = {4,2,0,3,2,5};
    int size = sizeof(height)/sizeof(height[0]);
    printf("%d\n", trap(height, size));
    return 0;
}

A Division by zero error

B Array index out of bounds error at right_max[heightSize]

C No error, outputs 9

D Segmentation fault due to null pointer

💡 Hint

Check array indexing carefully, especially at boundaries.

The code assigns right_max[heightSize] which is out of bounds since valid indices are 0 to heightSize-1. This causes undefined behavior or runtime error.

❓ Predict Output

advanced

Output of trapping rain water using stack approach

What is the output of this C code that calculates trapped rain water using a stack?

DSA C

#include <stdio.h>
#include <stdlib.h>

int trap(int* height, int heightSize) {
    int *stack = (int*)malloc(heightSize * sizeof(int));
    int top = -1;
    int water = 0;
    for (int i = 0; i < heightSize; i++) {
        while (top != -1 && height[i] > height[stack[top]]) {
            int top_height = height[stack[top--]];
            if (top == -1) break;
            int distance = i - stack[top] - 1;
            int bounded_height = (height[i] < height[stack[top]] ? height[i] : height[stack[top]]) - top_height;
            water += distance * bounded_height;
        }
        stack[++top] = i;
    }
    free(stack);
    return water;
}

int main() {
    int height[] = {0,2,0,3,0,1,0,4};
    int size = sizeof(height)/sizeof(height[0]);
    printf("%d\n", trap(height, size));
    return 0;
}

A 9

B 7

C 8

D 10

💡 Hint

Stack stores indices of bars; trapped water is calculated when a higher bar is found.

The stack approach calculates trapped water by popping lower bars and calculating bounded water between current and previous bars. For the input, total trapped water is 10 units.

🧠 Conceptual

expert

Time complexity analysis of trapping rain water algorithms

Which statement correctly describes the time complexity of the three common approaches to the trapping rain water problem: brute force, prefix/suffix max arrays, and two-pointer?

A Brute force is O(n^2), prefix/suffix max arrays is O(n^2), two-pointer is O(n)

B Brute force is O(n), prefix/suffix max arrays is O(n^2), two-pointer is O(n^2)

C Brute force is O(n^2), prefix/suffix max arrays is O(n), two-pointer is O(n)

D All three approaches have O(n) time complexity

💡 Hint

Consider how many times each element is processed in each approach.

Brute force checks max heights for each element scanning entire array, leading to O(n^2). Prefix/suffix max arrays precompute max heights in O(n) and then calculate water in O(n), total O(n). Two-pointer approach also runs in O(n) by scanning once from both ends.