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

Time Complexity: Trapping Rain Water Problem

O(n)

Understanding Time Complexity

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

Specifically, how the number of steps grows when we have more bars in the elevation map.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int trap(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) leftMax = height[left];
            else water += leftMax - height[left];
            left++;
        } else {
            if (height[right] >= rightMax) rightMax = height[right];
            else water += rightMax - height[right];
            right--;
        }
    }
    return water;
}
    

This code calculates how much water can be trapped between bars represented by an array of heights.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single while loop that moves two pointers from both ends towards the center.
• How many times: The loop runs until the two pointers meet, so roughly once per element in the array.

How Execution Grows With Input

As the number of bars increases, the loop runs once for each bar, so the steps grow directly with input size.

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

Pattern observation: The number of steps grows linearly as input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to solve the problem grows in direct proportion to the number of bars.

Common Mistake

[X] Wrong: "Because there are two pointers, the time is O(n²)."

[OK] Correct: Each pointer moves only forward and never goes back, so together they make at most n steps total, not n times n.

Interview Connect

Understanding this linear time solution shows you can optimize problems by clever pointer use instead of nested loops, a valuable skill in interviews.

Self-Check

"What if we used nested loops to check every pair of bars? How would the time complexity change?"