Trapping Rain Water Problem in DSA Python - Time & Space Complexity

Time Complexity: Trapping Rain Water Problem

O(n)

Understanding Time Complexity

We want to understand how the time taken to solve the Trapping Rain Water problem changes as the input size grows.

Specifically, how the number of operations depends on the number of bars in the elevation map.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def trap(height):
    n = len(height)
    left, right = 0, n - 1
    left_max, right_max = 0, 0
    water = 0
    while left <= right:
        if height[left] < height[right]:
            if height[left] > left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] > right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water
    

This code calculates how much water can be trapped between bars represented by the list height.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves two pointers across the array.
• How many times: Each element is visited at most once by either the left or right pointer, so total visits are proportional to the array length.

How Execution Grows With Input

As the number of bars increases, the loop runs once per bar, so operations grow linearly.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: Doubling the input size roughly doubles the number of operations.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute trapped water grows directly in proportion to the number of bars.

Common Mistake

[X] Wrong: "Because there are nested if-else statements, the time complexity must be quadratic O(n²)."

[OK] Correct: The if-else statements are inside a single loop that moves pointers only once through the array, so the total steps are still linear, not multiplied.

Interview Connect

Understanding this linear time solution shows you can optimize problems by clever pointer use instead of brute force, a skill highly valued in interviews.

Self-Check

"What if we used two nested loops to check water trapped at each bar? How would the time complexity change?"