Trapping Rain Water Using Stack 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 using a stack?

DSA C

int trap(int* height, int heightSize) {
    int stack[heightSize];
    int top = -1;
    int water = 0;
    int i = 0;
    while (i < heightSize) {
        while (top != -1 && height[i] > height[stack[top]]) {
            int topIndex = 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]]) - height[topIndex];
            water += distance * bounded_height;
        }
        stack[++top] = i++;
    }
    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]);
    int result = trap(height, size);
    printf("%d\n", result);
    return 0;
}

A 7

B 5

C 6

D 8

💡 Hint

Trace the stack operations and calculate trapped water between bars.

The code uses a stack to find boundaries and calculates trapped water between them. For the given input, the total trapped water units are 6.

❓ Predict Output

intermediate

Result of Trapping Rain Water for Different Input

What is the output of the trapping rain water function for this input array?

DSA C

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

A 9

B 8

C 7

D 6

💡 Hint

Calculate trapped water between bars using stack logic.

The trapped water units for the input {4,2,0,3,2,5} is 9.

🔧 Debug

advanced

Identify the Error in Stack Implementation

What error will occur if the stack array is declared as int stack[heightSize-1] instead of int stack[heightSize] in the trapping rain water code?

DSA C

int stack[heightSize-1];
int top = -1;
// rest of the code unchanged

A No error, code runs fine

B Buffer overflow when pushing last element

C Stack underflow error during pop

D Compilation error due to invalid array size

💡 Hint

Consider the maximum number of elements pushed onto the stack.

The stack size must be at least heightSize to hold all indices. Using heightSize-1 causes buffer overflow when pushing the last index.

🧠 Conceptual

advanced

Why Use Stack for Trapping Rain Water?

Why is a stack used in the trapping rain water problem instead of a simple two-pointer approach?

A Stack helps track previous bars to calculate bounded water efficiently

B Stack reduces time complexity from O(n) to O(log n)

C Stack automatically sorts the bars for easier calculation

D Stack avoids the need to traverse the array multiple times

💡 Hint

Think about how the stack stores indices of bars and helps find boundaries.

Stack stores indices of bars in increasing height order to find boundaries and calculate trapped water efficiently in one pass.

🚀 Application

expert

Maximum Water Trapped with Modified Input

Given the input array {5,2,1,2,1,5}, what is the maximum amount of water trapped calculated by the stack method?

A 12

B 15

C 13

D 14

💡 Hint

Visualize the bars and calculate trapped water between boundaries.

The trapped water units for {5,2,1,2,1,5} is 14 units.