Container With Most Water in DSA C - Time & Space Complexity

Time Complexity: Container With Most Water

O(n)

Understanding Time Complexity

We want to find how fast the algorithm finds the container holding the most water.

How does the time taken grow as the number of lines (heights) increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int maxArea(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int max_area = 0;
    while (left < right) {
        int width = right - left;
        int h = height[left] < height[right] ? height[left] : height[right];
        int area = width * h;
        if (area > max_area) max_area = area;
        if (height[left] < height[right]) left++;
        else right--;
    }
    return max_area;
}
    

This code finds the largest water container by moving two pointers from both ends towards the center.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves pointers inward.
• How many times: At most, it runs once for each element, so about n times.

How Execution Grows With Input

As the number of lines increases, the loop runs roughly once per line.

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

Pattern observation: The operations grow linearly with input size.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

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

[OK] Correct: Each pointer moves only forward or backward once, so total steps are at most n, not n times n.

Interview Connect

Understanding this linear time approach shows you can optimize by avoiding unnecessary checks, a key skill in problem solving.

Self-Check

"What if we used a nested loop to check every pair? How would the time complexity change?"