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

Time Complexity: Container With Most Water

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the container with the most water changes as the number of lines grows.

How does the number of steps grow when we have more lines to check?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    def max_area(height):
        left, right = 0, len(height) - 1
        max_water = 0
        while left < right:
            width = right - left
            current_height = min(height[left], height[right])
            max_water = max(max_water, width * current_height)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_water
    

This code finds the maximum 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 the left and right pointers towards each other.
• How many times: At most, it runs once for each element from both ends, so about n times where n is the number of lines.

How Execution Grows With Input

As the number of lines increases, the number of steps grows roughly in a straight line.

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

Pattern observation: The steps increase directly with the number of lines, so doubling the lines roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the max water grows in a straight line with the number of lines.

Common Mistake

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

[OK] Correct: The pointers only move inward once each step, so total steps are just n, not n times n.

Interview Connect

Understanding this linear time approach shows you can find efficient solutions by smartly moving pointers instead of checking all pairs.

Self-Check

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