Big O Gym › Problem

Big O Practice: Container With Most Water

Time and space complexity practice in Python and JavaScript. Concept tested: monotone two-pointer convergence.

def max_area(heights):
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        h = min(heights[left], heights[right])
        best = max(best, h * (right - left))
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return best

Variables

  • n - length of the heights array

Explanation

Pointers move toward each other, each step advancing one of them - **O(n)** total iterations. Only two indices and one running max are kept, **O(1)** space. The greedy choice (always advance the shorter side) is what unlocks linearity.

More Big O practice problems · Today's daily problem