Trapping Rain Water Using Stack in DSA Python - 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 with the bars in the stack.

beginner

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

Each element represents the index of a bar in the elevation map, helping to find boundaries for trapped water.

intermediate

Why do we pop from the stack when the current bar height is greater than the height of the bar at the top of the stack?

Because we found a right boundary taller than the bar at the top, allowing us to calculate trapped water between boundaries.

intermediate

How is the width of trapped water calculated in the stack method?

Width is the distance between the current index and the new top of the stack minus one, representing the horizontal space between boundaries.

beginner

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.

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

A Indices of bars

B Heights of bars

C Water trapped at each bar

D Widths between bars

The stack stores indices of bars to help calculate trapped water between boundaries.

When do we calculate trapped water in the stack approach?

A Before pushing any bar

B When current bar is shorter than top of stack

C At the end of the array only

D When current bar is taller than top of stack

We calculate trapped water when the current bar is taller than the bar at the top of the stack.

What does popping from the stack represent in this problem?

A Removing a boundary bar

B Calculating trapped water between boundaries

C Finding a valley to trap water

D Resetting the stack

Popping helps calculate trapped water between the current bar and the new top of the stack.

How is the trapped water height calculated after popping from the stack?

A Sum of current and top bar heights minus popped bar height

B Maximum of current and top bar heights minus popped bar height

C Minimum of current and top bar heights minus popped bar height

D Difference between current and popped bar heights

Height is the minimum of current and top bar heights minus the popped bar height.

What is the overall time complexity of the stack solution for trapping rain water?

A O(n)

B O(n log n)

C O(log n)

D O(n^2)

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

Explain step-by-step how the stack helps calculate trapped rain water in the elevation map.

Think about how boundaries form valleys to hold water.

Describe how to calculate the width and height of trapped water when popping from the stack.

Focus on how boundaries define the trapped water area.

Practice

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

easy

A. To store the total amount of trapped water

B. To sort the heights of bars in ascending order

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

D. To reverse the order of the height array

Solution

1. Step 1: Understand the role of the stack

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

2. Step 2: Why not other options?

   The stack does not store water amount 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 C

4. Quick Check:

   Stack tracks bars for trapping water = B [OK]

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

Common Mistakes:

• Thinking stack stores water amount
• Assuming stack sorts the bars
• Believing stack reverses the array

2. Which of the following Python code snippets correctly initializes an empty stack for the trapping rain water algorithm?

easy

A. stack = 0

B. stack = {}

C. stack = None

D. stack = []

Solution

1. Step 1: Identify correct stack initialization

   In Python, a stack is commonly represented by a list, so stack = [] initializes an empty stack.

2. Step 2: Why other options are wrong

   {} is a dictionary, None is no value, and 0 is an integer, none suitable for stack operations.

3. Final Answer:

   stack = [] -> Option D

4. Quick Check:

   Empty list for stack = A [OK]

Hint: Use empty list [] to create stack in Python [OK]

Common Mistakes:

• Using {} which creates a dictionary
• Assigning None instead of list
• Using integer 0 as stack

3. What is the output of the following code snippet that uses stack to calculate trapped rain water?

def trap(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            top = stack.pop()
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height[stack[-1]], h) - height[top]
            water += distance * bounded_height
        stack.append(i)
    return water

print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))

medium

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace the algorithm with given heights

   The code calculates trapped water for heights [0,1,0,2,1,0,1,3,2,1,2,1]. The total trapped water is 6 units.

2. Step 2: Confirm calculation matches known example

   This is a classic example where trapped water is 6, matching the output of the code.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Trapped water = 6 [OK]

Hint: Classic example trap water = 6 units [OK]

Common Mistakes:

• Miscounting trapped water units
• Ignoring stack pop conditions
• Wrong distance or bounded height calculation

4. Identify the error in the following code snippet for trapping rain water using stack:

def trap(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] <= h:
            top = stack.pop()
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height[stack[-1]], h) - height[top]
            water += distance * bounded_height
        stack.append(i)
    return water

print(trap([4,2,0,3,2,5]))

medium

A. The distance calculation is incorrect

B. The condition should be < instead of <=

C. The stack should be a queue

D. The water variable should be initialized to 1

Solution

1. Step 1: Check the while loop condition

   The condition height[stack[-1]] <= h causes popping even when heights are equal, which is incorrect for trapping water calculation.

2. Step 2: Correct condition and reason

   It should be height[stack[-1]] < h to pop only when current height is strictly greater, ensuring correct water trapping.

3. Final Answer:

   The condition should be < instead of <= -> Option B

4. Quick Check:

   Use < not <= in while condition [OK]

Hint: Use strict less than < in stack pop condition [OK]

Common Mistakes:

• Using <= causes wrong popping
• Confusing stack with queue
• Incorrect distance formula
• Initializing water to 1 instead of 0

5. Given the height array [3, 0, 2, 0, 4], what is the total trapped rain water calculated using the stack method? Explain how the stack helps in this calculation.

hard

A. 4

B. 7

C. 5

D. 6

Solution

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

   Heights: [3,0,2,0,4]. Water trapped at position 1 is 3 units, at position 2 is 0 units, at position 3 is 1 unit. Total trapped water = 4 units.

2. Step 2: Explain stack role in calculation

   The stack stores indices of bars. When a higher bar is found, it pops lower bars and calculates trapped water using distance and bounded height between bars.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Stack helps find boundaries; trapped water = 4 [OK]

Hint: Stack finds left/right boundaries to calculate trapped water [OK]

Common Mistakes:

• Adding trapped water incorrectly
• Ignoring zero height bars
• Not using stack to find boundaries