1. Problem understanding

Given an array height where height[i] is the height of a vertical line at x = i, find two lines that together with the x-axis form a container that holds the most water. Return the maximum area possible. Area between lines i and j is (j - i) * min(height[i], height[j]).

2. Clarifying questions

• What are input constraints? (max n, height[i] range)

• Are heights non-negative integers?

• Can n be 0 or 1? What should we return then? (usually 0)

• Any memory/time limits I should aim for? (expect O(n) time, O(1) space)

• Are indices zero-based? (usually yes)

• Do we need to return the indices or the area? (problem asks for area)

3. Walkthrough examples

• [] → 0

• [1] → 0

• [1,1] → 1 (width 1 × min(1,1)=1)

• [1,8,6,2,5,4,8,3,7] → 49 (classic example)

4. Brainstorm solutions (2–3) and compare

4.1. Brute-force (naive)

• Try all pairs (i, j), compute area.

• Time: O(N^2)

• Space: O(1)

4.2. Two-pointer (optimal, standard)

• Place l = 0, r = n-1. Compute area, move the pointer at the shorter line inward (because moving the taller won’t increase min height). Repeat while l < r.

=> Moving the smaller height, to increase the height, because j - i is decrease => we need the height[min] is increase

• Time: O(N).

• Space: O(1).

5. Implement solutions

5.1. Brute Force

class Solution:
    def maxArea(self, heights: List[int]) -> int:
        res = 0
        for i in range(len(heights)):
            for j in range(i + 1, len(heights)):
                res = max(res, min(heights[i], heights[j]) * (j - i))
        return res

• Time: O(N^2).

• Space: O(1).

5.2. Two Pointers

class Solution:
    def maxArea(self, heights: List[int]) -> int:
        l, r = 0, len(heights) - 1
        res = 0

        while l < r:
            area = min(heights[l], heights[r]) * (r - l)
            res = max(res, area)
            if heights[l] <= heights[r]:
                l += 1
            else:
                r -= 1
        return res

• Time: O(N).

• Space: O(1).

Why move the shorter side?

The area is limited by the shorter line.

• Moving the taller line inward can’t increase the height (the limiting factor remains the same or worse), and width decreases — so area can’t increase.

• Only by moving the shorter line can we possibly find a taller line that increases the minimum height — giving a chance for a larger area.

6. Run the testcases

heights = [1,8,6,2,5,4,8,3,7]

l	r	heights[l]	heights[r]	min	width	area	res	Move
0	8	1	7	1	8	8	8	l++
1	8	8	7	7	7	49	49	r--
1	7	8	3	3	6	18	49	r--
1	6	8	8	8	5	40	49	r--
1	5	8	4	4	4	16	49	r--
1	4	8	5	5	3	15	49	r--
1	3	8	2	2	2	4	49	r--
1	2	8	6	6	1	6	49	r--
1	1	—	—	—	—   —   49  stop