Trapping Rainwater: 2 Powerful Approaches Using Stack and Queue

Trapping rainwater is a well-known coding problem in data structures and algorithms that tests problem-solving skills and efficiency in handling water retention problems. Among the various solutions available, two powerful approaches stand out: using a Stack and using a Queue. These approaches help optimize time complexity while ensuring an efficient way to compute trapped rainwater.

In this blog, we’ll dive deep into the trapping rainwater problem, discuss how stack and queue can be used to solve it, and compare both approaches with code implementations.

Understanding the Trapping Rainwater Problem

The trapping rainwater problem is defined as follows:

• Given an array of non-negative integers, where each element represents the height of a bar in a histogram, determine how much rainwater can be trapped between these bars after rainfall.

Example

Input: [3, 0, 2, 0, 4]
Output: 7

Explanation

The water trapped in this histogram is as follows:

      #
#     #
#  #  #
#  #  #

The total trapped water = 3 units (between bars at index 0 and 2) + 2 units (between index 2 and 4) + 2 units (between index 3 and 4) = 7 units.

Also Read: 7 Steps to Master the Painter’s Partition Problem

Approach 1: Using Stack for Trapping Rainwater

How It Works

The stack-based approach efficiently computes the trapped water by storing indices of the bars in a monotonic stack. The key idea is to process elements from left to right while keeping track of elevation levels.

Algorithm

1. Initialize an empty stack and a variable water = 0.
2. Iterate through the array using an index i.
3. While the stack is not empty and the current height is greater than the height at the top of the stack:
   • Pop the stack and store the top index.
   • If the stack becomes empty, break (no boundary to trap water).
   • Find the trapped water using distance × min(height[left], height[right]) - height[current].
4. Push the current index onto the stack.
5. Repeat the process until the array is traversed.

Code Implementation (Python)

def trap_rainwater_stack(heights):
    stack = []
    trapped_water = 0

    for i in range(len(heights)):
        while stack and heights[i] > heights[stack[-1]]:
            top = stack.pop()

            if not stack:
                break

            distance = i - stack[-1] - 1
            bounded_height = min(heights[i], heights[stack[-1]]) - heights[top]
            trapped_water += distance * bounded_height

        stack.append(i)

    return trapped_water

# Example
heights = [3, 0, 2, 0, 4]
print(trap_rainwater_stack(heights))  # Output: 7

Time Complexity

• O(n) – Each element is pushed and popped at most once.

Space Complexity

• O(n) – Due to stack storage.

Also Read: Master Python Decorators: A Complete Guide to Implement Decorators in Python

Approach 2: Using Queue for Trapping Rainwater

How It Works

A queue-based approach can also be used, but it follows a breadth-first search (BFS)-like strategy to track the maximum boundary heights.

Algorithm

1. Use two pointers (left and right) to traverse from both ends.
2. Maintain two boundary heights (left_max and right_max).
3. If height[left] is smaller than height[right]:
   • Update left_max and calculate trapped water accordingly.
   • Move left forward.
4. Otherwise:
   • Update right_max and compute trapped water.
   • Move right backward.
5. Continue until both pointers meet.

Also Read: How to Build a Secure Password Manager with Next.js, Clerk, Tailwind CSS & Shadcn UI

Code Implementation (Python)

def trap_rainwater_queue(heights):
    if not heights:
        return 0

    left, right = 0, len(heights) - 1
    left_max, right_max = heights[left], heights[right]
    trapped_water = 0

    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, heights[left])
            trapped_water += max(0, left_max - heights[left])
        else:
            right -= 1
            right_max = max(right_max, heights[right])
            trapped_water += max(0, right_max - heights[right])

    return trapped_water

# Example
heights = [3, 0, 2, 0, 4]
print(trap_rainwater_queue(heights))  # Output: 7

Time Complexity

• O(n) – Each element is processed once.

Space Complexity

• O(1) – Uses only a few extra variables.

Stack vs. Queue Approach: Which One is Better?

Aspect	Stack Approach	Queue Approach
Time Complexity	O(n)	O(n)
Space Complexity	O(n)	O(1)
Processing Order	Uses a stack to track previous indices	Uses two pointers for left-right traversal
Efficiency	Works well for complex boundaries	Faster and memory-efficient

Which One to Choose?

• Use Stack when handling irregular terrain with complex trapping patterns.
• Use Queue (Two Pointers) for optimal efficiency in memory and speed.

FAQs

How does stack help in trapping rainwater?
A stack keeps track of previous bars to compute trapped water efficiently when encountering a higher elevation.

Why is the queue approach more space-efficient?
It uses only a few extra variables instead of storing indices, making it O(1) in space.

Which approach is best for large datasets?
The queue-based approach is preferable due to its O(1) space complexity.

Can this problem be solved using dynamic programming?
Yes, an alternative DP-based approach stores precomputed max heights but requires additional memory.

What is the key takeaway from this problem?
Understanding stack and queue can help in many algorithmic challenges, especially in water trapping, histogram problems, and flood-fill algorithms.

Conclusion

The trapping rainwater problem is an essential coding challenge that can be solved efficiently using stack and queue. While the stack-based approach helps in tracking previous elevations, the queue (two-pointer) approach optimizes memory usage and processing speed. Choosing the best approach depends on problem constraints and efficiency requirements.

🚀 Ready to enhance your coding skills? Start implementing these approaches today!