Trapping Rain Water Using Stack in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a stack to solve the Trapping Rain Water problem?

Use a stack to keep track of bars that are bounded by higher bars on both sides. When a higher bar is found, calculate trapped water using the distance and height difference between bars.

beginner

In the stack approach, what does each element in the stack represent?

Each element represents the index of a bar in the height array, stored to help calculate trapped water when a higher bar is encountered.

intermediate

Why do we pop from the stack when the current bar is higher than the top of the stack in the Trapping Rain Water problem?

Because a higher bar on the right means we can calculate trapped water with the popped bar as the bottom, bounded by the current bar and the new top of the stack.

intermediate

What is the time complexity of the Trapping Rain Water solution using a stack?

O(n), because each bar is pushed and popped at most once from the stack.

advanced

Explain how trapped water is calculated between bars using the stack method.

Calculate distance between current bar and new top of stack minus one. Height is minimum of current and top bar heights minus popped bar height. Multiply distance by height to get trapped water volume.

What does the stack store in the Trapping Rain Water problem?

A Indices of bars

B Heights of bars

C Water volumes

D Distances between bars

The stack stores indices of bars to help calculate trapped water when a higher bar is found.

When do we calculate trapped water in the stack approach?

A When current bar is higher than stack top

B When current bar is lower than stack top

C When stack is empty

D At the end of the array only

Trapped water is calculated when the current bar is higher than the top of the stack.

What is the time complexity of the stack-based Trapping Rain Water solution?

A O(n^2)

B O(n)

C O(log n)

D O(n log n)

Each bar is pushed and popped at most once, so the time complexity is O(n).

What does the 'distance' represent when calculating trapped water using the stack?

A Height difference between bars

B Index of the current bar

C Total water trapped so far

D Number of bars between current and stack top minus one

Distance is the horizontal gap between the current bar and the new top of the stack minus one.

Why do we use the minimum height of current and stack top bars in water calculation?

A To calculate the total height of bars

B To find the tallest bar

C To find the lowest boundary for water trapping

D To ignore the popped bar height

The minimum height of the two bars forms the boundary that limits how much water can be trapped.

Describe step-by-step how the stack is used to calculate trapped rain water.

Think about how the stack helps find boundaries for water trapping.

Explain why the stack-based approach is efficient compared to brute force for trapping rain water.

Consider how many times each bar is pushed or popped.

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