Trapping Rain Water Using Stack in DSA C - Build from Scratch

Trapping Rain Water Using Stack

📖 Scenario: Imagine you have a row of buildings with different heights. When it rains, water can get trapped between these buildings. We want to find out how much water is trapped after the rain.

🎯 Goal: Build a program in C that uses a stack to calculate the total amount of trapped rain water between buildings of different heights.

📋 What You'll Learn

Create an array called height with exact values representing building heights

Create an integer variable n for the number of buildings

Use a stack implemented with an integer array and a top pointer

Use a loop to process each building height and calculate trapped water using the stack

Print the total trapped water as an integer

💡 Why This Matters

🌍 Real World

Calculating trapped rain water helps in urban planning and designing drainage systems to prevent flooding.

💼 Career

Understanding stack-based algorithms is useful for software engineers working on problems involving data processing, simulations, and optimization.

1

Create the building heights array

Create an integer array called height with these exact values: 0,1,0,2,1,0,1,3,2,1,2,1. Also create an integer variable n and set it to 12.

DSA C

# Create the array height and variable n
// Your code here

Hint

Use int height[] = {...}; to create the array and int n = 12; for the size.

2

Set up the stack and variables

Create an integer array called stack of size n to use as the stack. Create an integer variable top and set it to -1. Create an integer variable water and set it to 0 to store total trapped water.

DSA C

int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12;
// Create stack array, top, and water variables
// Your code here

Hint

Use int stack[12]; for the stack, int top = -1; for empty stack, and int water = 0; to count water.

3

Calculate trapped water using the stack

Write a for loop with variable i from 0 to n-1. Inside the loop, while top != -1 and height[i] > height[stack[top]], pop the top of the stack into topIndex. If after popping the stack is empty (top == -1), break the loop. Otherwise, calculate the distance as i - stack[top] - 1 and bounded height as the minimum of height[i] and height[stack[top]] minus height[topIndex]. Add distance * bounded_height to water. After the while loop, push i onto the stack by incrementing top and setting stack[top] = i.

DSA C

int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12;
int stack[12];
int top = -1;
int water = 0;
// Write for loop and stack logic to calculate trapped water
// Your code here

Hint

Use a for loop over i. Inside, use a while loop to pop from stack while current height is greater. Calculate distance and bounded height, then add to water. Push current index onto stack.

4

Print the total trapped water

Write a printf statement to print the integer value of water.

DSA C

int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12;
int stack[12];
int top = -1;
int water = 0;

for (int i = 0; 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;
}
// Print the total trapped water
// Your code here

Hint

Use printf("%d\n", water); to print the total trapped water.