Trapping Rain Water Using Stack in DSA Python - Time & Space Complexity

Time Complexity: Trapping Rain Water Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time taken grows when we use a stack to solve the trapping rain water problem.

How does the number of steps change as the height list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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(h, height[stack[-1]]) - height[top]
            water += distance * bounded_height
        stack.append(i)
    return water

This code calculates how much water can be trapped after raining using a stack to track bars.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop goes through each bar once, and the while-loop pops bars from the stack when the current bar is taller.
• How many times: Each bar is pushed and popped at most once, so the total number of stack operations is at most 2n for n bars.

How Execution Grows With Input

As the number of bars increases, the total steps grow roughly in a straight line with the number of bars.

Input Size (n)	Approx. Operations
10	About 20 stack operations
100	About 200 stack operations
1000	About 2000 stack operations

Pattern observation: The operations grow linearly, doubling the input roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows directly in proportion to the number of bars in the input.

Common Mistake

[X] Wrong: "The nested while-loop makes this algorithm O(n²) because it looks like a loop inside a loop."

[OK] Correct: Each bar is pushed and popped only once, so the total number of operations is still proportional to n, not n squared.

Interview Connect

Understanding this stack approach shows you can use data structures smartly to solve problems efficiently, a skill valued in many coding challenges.

Self-Check

"What if we used a simple nested loop instead of a stack? How would the time complexity change?"