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.

Practice

1. What is the main purpose of using a stack in the Trapping Rain Water Using Stack algorithm?

easy

A. To reverse the order of the bars

B. To store the total amount of trapped water directly

C. To sort the heights of bars in ascending order

D. To keep track of bars that are not yet processed for water trapping

Solution

1. Step 1: Understand stack role in the algorithm

   The stack stores indices of bars that are waiting to find a right boundary to trap water.

2. Step 2: Clarify what the stack does not do

   The stack does not store water amounts or sort bars; it helps find boundaries for trapped water.

3. Final Answer:

   To keep track of bars that are not yet processed for water trapping -> Option D

4. Quick Check:

   Stack tracks bars for trapping water [OK]

Hint: Stack holds indices of bars waiting for right boundary [OK]

Common Mistakes:

• Thinking stack stores water volume directly
• Assuming stack sorts the bars
• Believing stack reverses bar order

2. Which of the following C code snippets correctly declares a stack to store indices for trapping rain water?

easy

A. int stack[100]; int top = -1;

B. int stack; int top = 0;

C. int *stack = NULL; int top = 1;

D. int stack[] = {}; int top = -1;

Solution

1. Step 1: Check stack declaration syntax

   int stack[100]; int top = -1; declares an integer array with fixed size and initializes top to -1, which is correct for stack implementation.

2. Step 2: Identify incorrect declarations

   Options B, C, and D have wrong types or invalid initializations for stack and top pointer.

3. Final Answer:

   int stack[100]; int top = -1; -> Option A

4. Quick Check:

   Array + top = -1 is correct stack setup [OK]

Hint: Use array and top = -1 for empty stack [OK]

Common Mistakes:

• Using uninitialized or wrong top value
• Declaring stack as single int instead of array
• Using empty array syntax invalid in C

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

int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12;
// Assume correct trapping rain water stack code runs here
int trapped = trappingRainWater(height, n);
printf("%d\n", trapped);

medium

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Understand the input heights

   The array represents bar heights where water can be trapped between taller bars.

2. Step 2: Calculate trapped water manually or recall known result

   The known trapped water for this input is 6 units.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Standard example trapped water = 6 [OK]

Hint: Remember classic example traps 6 units water [OK]

Common Mistakes:

• Miscounting trapped water units
• Confusing indexes or heights
• Assuming output is sum of heights

4. Identify the bug in this snippet of the trapping rain water stack algorithm:

while (top != -1 && height[i] > height[stack[top]]) {
  int topIndex = stack[top--];
  int distance = i - stack[top] - 1;
  int bounded_height = min(height[i], height[stack[top]]) - height[topIndex];
  water += distance * bounded_height;
}

medium

A. Using 'min' function without including its definition or header

B. Incorrect calculation of 'distance' by missing parentheses

C. Wrong decrement of 'top' causing stack underflow

D. Using 'water' variable without initialization

Solution

1. Step 1: Check function usage

   The code uses 'min' function but C standard library does not have 'min' by default; it needs a macro or function definition.

2. Step 2: Verify other parts

   Distance calculation and top decrement are correct; water variable usage depends on context but usually initialized.

3. Final Answer:

   Using 'min' function without including its definition or header -> Option A

4. Quick Check:

   min() undefined in C without custom code [OK]

Hint: Remember C needs custom min function or macro [OK]

Common Mistakes:

• Assuming min() is built-in in C
• Miscalculating distance with wrong parentheses
• Forgetting to initialize water variable

5. Given the heights array {4, 2, 0, 3, 2, 5}, what is the total trapped rain water calculated using the stack method?

hard

A. 8

B. 7

C. 9

D. 6

Solution

1. Step 1: Analyze the heights for trapped water

   Water trapped at each position i is max(0, min(left_max[i], right_max[i]) - height[i]), where left_max is tallest bar strictly to the left, right_max strictly to the right. Stack method yields same result.

2. Step 2: Calculate trapped water step-by-step

   - i=1: min(4,5)-2 = 2
   - i=2: min(4,5)-0 = 4
   - i=3: min(4,5)-3 = 1
   - i=4: min(4,5)-2 = 2
   Total: 2+4+1+2 = 9 units.

3. Final Answer:

   9 -> Option C

4. Quick Check:

   Total trapped water = 9 [OK]

Hint: Sum water trapped between boundaries carefully [OK]

Common Mistakes:

• Double counting trapped water
• Ignoring zero height bars
• Misidentifying boundaries