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

Time Complexity: Trapping Rain Water Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to calculate trapped rain water changes as the input size grows.

Specifically, how the steps increase when using a stack to solve this problem.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int trap(int* height, int heightSize) {
    int stack[heightSize];
    int top = -1, water = 0, current = 0;
    while (current < heightSize) {
        while (top != -1 && height[current] > height[stack[top]]) {
            int topIndex = stack[top--];
            if (top == -1) break;
            int distance = current - stack[top] - 1;
            int bounded_height = (height[current] < height[stack[top]] ? height[current] : height[stack[top]]) - height[topIndex];
            water += distance * bounded_height;
        }
        stack[++top] = current++;
    }
    return water;
}
    

This code calculates how much rain water can be trapped between bars using a stack to track boundaries.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer while loop runs through each bar once.
• Inner loop: The inner while loop pops bars from the stack when current bar is taller.
• How many times: Each bar is pushed and popped at most once, so total operations scale with input size.

How Execution Grows With Input

As the number of bars increases, each bar is processed a limited number of times.

Input Size (n)	Approx. Operations
10	About 20 (push and pop each bar once)
100	About 200
1000	About 2000

Pattern observation: The operations grow roughly in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The inner loop causes the time to be quadratic (O(n²)) because it is nested inside the outer loop."

[OK] Correct: Each bar is pushed and popped only once, so total inner loop executions across all iterations add up to n, not n².

Interview Connect

Understanding this time complexity shows you can analyze stack-based solutions and explain why they are efficient, a valuable skill in interviews.

Self-Check

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