DSA sheet · Arrays · Two Pointers pattern

Container With Most Water

The teacher calls this one of the most asked and most famous interview questions. We get the heights of vertical lines and must pick two lines that hold the most water between them. She first writes the brute force (try every pair, O(n²)), shows from the constraints that it will time out, and then uses opposite-end two pointers. The whole trick is one decision: after measuring a container, which wall do we move inward?

Why it matters: it shows that two pointers don't need a sorted array; they need a rule that tells you which pointer can safely move. That rule ("move the shorter wall") comes back in Trapping Rain Water right after this.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (two pointers from scratch)
• Part A · Brute force: every pair of lines
• Part B · Optimal: two pointers, move the shorter wall
• Part C · Revision page

Part 0 · Before starting

What is a pointer here?

A pointer is just a variable holding an index into the array. "left points to 2" means left = 2, and height[left] is the value there.

The brute force over all pairs, and when we can skip pairs

When an answer depends on two positions (i, j), the simplest plan is two nested loops over every pair: n·(n−1)/2 pairs, which is O(n²). Two pointers is a way to skip whole groups of pairs because we can prove they can't beat what we already have. Usually that proof comes from the array being sorted. In this problem it comes from the area formula itself (Part B).

Opposite-end pointers

left starts at index 0 and right at index n − 1. Each step we look at the pair (left, right), then move exactly one of them inward. They meet after about n steps, so the work is O(n). The only hard part is the rule for which one to move. The rule must guarantee that the pointer we move away from can't be part of a better answer, so no good pair is ever skipped.

Why two pointers and not sliding window, prefix sum or Kadane's?

The teacher's four array patterns are two pointers, sliding window, prefix sum and Kadane's. The last three are for a contiguous subarray where every value in between matters (a sum, an average, a length under some rule). Here the area uses only the two chosen lines: the shorter height and the distance between them. The lines in between don't change the area at all. "Two points, nothing in between" → two pointers.

Part A · Brute force: every pair of lines

LeetCode 11

1The question in simple words

You get a list height of n numbers. Imagine n vertical lines (planks) standing on the x-axis: line i stands at x = i and is height[i] tall. Choose two lines. Together with the floor they form a container. Return the largest amount of water any such container can hold. You can't tilt the container.

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

   8 |    █              █
   7 |    █~~~~~~~~~~~~~~█~~~~~█
   6 |    █~~█~~~~~~~~~~~█~~~~~█
   5 |    █~~█~~~~~█~~~~~█~~~~~█
   4 |    █~~█~~~~~█~~█~~█~~~~~█
   3 |    █~~█~~~~~█~~█~~█~~█~~█
   2 |    █~~█~~█~~█~~█~~█~~█~~█
   1 | █  █~~█~~█~~█~~█~~█~~█~~█
     +---------------------------
       0  1  2  3  4  5  6  7  8      ~ = water between line 1 and line 8

The best choice is line 1 (height 8) and line 8 (height 7). Water can only rise to 7 (the shorter one), and they are 8 − 1 = 7 apart. Area = 7 × 7 = 49.

2What the constraints tell us

• 2 ≤ n ≤ 10⁵. There are always at least two lines. n² would be 10¹⁰, far beyond the ~10⁸ steps that pass in time, so O(n²) will give TLE. We need O(n) (or O(n log n)).
• 0 ≤ height[i] ≤ 10⁴. The teacher's point: n tells us how fast the code must be; the values tell us what type to store them in. The largest area is about 10⁴ × 10⁵ = 10⁹, which still fits in a normal int (limit about 2.1 × 10⁹). In Python, ints never overflow anyway. Height 0 is allowed, so some containers hold 0.

3Intuition: the shorter line decides the level

Pour water between two lines. It rises until it reaches the top of the shorter line; any more spills over that side. So:

The brute force just tries this for every pair and keeps the biggest.

4Building the logic from the example

First pairs: line 0 with everyone after it

• Lines 0 and 1 (heights 1 and 8): shorter = 1, width = 1 − 0 = 1 → area 1.
• Lines 0 and 2 (1 and 6): shorter = 1, width = 2 → area 2.
• Lines 0 and 3: 1 × 3 = 3 … and so on up to line 8.

Then line 1 with every line after it, then line 2 with every line after it, and so on. That's two loops: left goes over every index, and right goes from left + 1 to the end. Starting right at left + 1 means we never pair a line with itself and never count the same pair twice.

Keeping the best

Each area is compared with a max_area variable that lives outside both loops: max_area = max(max_area, area). After the loops, it holds the answer.

5Approach steps

1. max_area = 0.
2. For every left from 0 to n − 1, for every right from left + 1 to n − 1:
3. height of water = min of the two lines, width = right − left, area = height × width.
4. Update max_area.
5. Return max_area.

6Code (Python)

class Solution:
    def maxArea(self, height):
        n = len(height)
        max_area = 0
        for left in range(n):
            for right in range(left + 1, n):
                h = min(height[left], height[right])   # water stops at the shorter line
                w = right - left                       # distance between the lines
                max_area = max(max_area, h * w)
        return max_area

7Code line by line

8Dry run (hand table, first rows)

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

36 pairs in total for n = 9. The answer is 49.

9Complexity & remember

• Time O(n²): for left = 0, right takes n − 1 values; for left = 1, n − 2 values; … That adds up to about n²/2. With n = 10⁵ that's about 10¹⁰ → TLE.
• Space O(1).

Part B · Optimal: two pointers, move the shorter wall

LeetCode 11

1The question again, with the new goal

Same question, now in O(n): one sweep where left starts at the first line, right at the last, and one of them moves inward every step.

2"But two pointers needs a sorted array…"

The teacher raises this herself. In earlier problems the array was sorted, and that's what told us which pointer to move. Here the heights are not sorted. Her answer: sorting was never the goal. It was only a way to decide which pointer to move. If we can make that decision some other way, we can still use two pointers. Here the area formula gives us the rule.

3Intuition: start as wide as possible, then trade width for height

Start with the widest container: line 0 and line n − 1. From now on, any move makes the container narrower, by one. Area = height × width, and the width only shrinks. So the only hope of a bigger area is to find a taller water level. That gives a greedy idea: keep the taller wall and throw away the shorter one, hoping the next line is taller.

4Building the rule: why moving the shorter wall is the only move that can help

Her small example: walls of height 2 and 5, three apart

Left wall 2 (at index 2), right wall 5 (at index 5). Width 3, level min(2, 5) = 2, area 2 × 3 = 6. Now we must move one wall inward. Which one?

• Move the taller wall (5) inward: the 2 stays. The new width is smaller. The new level is min(2, something), which is at most 2, however tall the new line is. Smaller width × level ≤ 2 → always less than 6. This move can never help.
• Move the shorter wall (2) inward: the 5 stays. The width is smaller, but the level is now min(new line, 5). If the new line is taller than 2, the level goes up (as high as 5). This is the only way the area might grow.

The full reason: the shorter wall has already done its best

Say height[left] ≤ height[right]. Think about every container that still uses line left, paired with any line between left and right:

• Its width is less than right − left (the partner is closer).
• Its level is min(height[left], partner) ≤ height[left], which is no more than the level we have right now.

Narrower and not higher → every one of those containers is ≤ the area we just measured. So line left has nothing better to offer: its best container is the one we already recorded. Dropping it (left += 1) can't skip the answer. That's why the shorter wall is the one to move.

5Approach steps

1. left = 0, right = n − 1, max_area = 0.
2. While left < right:
3. area = min(height[left], height[right]) × (right − left); update max_area.
4. If height[left] ≤ height[right] → left += 1; else → right -= 1.
5. Return max_area.

6Code (Python)

class Solution:
    def maxArea(self, height):
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:                            # need two different lines
            h = min(height[left], height[right])       # level = shorter wall
            w = right - left                           # width
            max_area = max(max_area, h * w)
            if height[left] <= height[right]:          # left is the shorter wall
                left += 1                              # its best is already counted
            else:
                right -= 1                             # right is shorter: drop it
        return max_area

On screen the teacher first typed the width the wrong way round, got a wrong answer, and fixed it to right − left ("my bad"). If your answers come out negative or tiny, check the width first.

7Code line by line

8Dry run

height = [1, 8, 6, 2, 5, 4, 8, 3, 7], n = 9. This is the same walk the teacher does on screen.

The array at key moments. Yellow = the two walls being measured, grey = lines already thrown away.

Only 8 containers measured instead of 36, and none of the skipped ones could have beaten 49.

9Complexity & remember

• Time O(n): each step moves one pointer one place inward, and they stop when they meet. The teacher's way: if left walks 4 places and right walks 5, together they covered the array once. So about n steps in total.
• Space O(1): two indexes and one number.

Part C · Revision page

s = Solution()
print(s.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))   # 49
print(s.maxArea([1, 1]))                        # 1
print(s.maxArea([4, 3, 2, 1, 4]))               # 16
print(s.maxArea([0, 0]))                        # 0
print(s.maxArea([1, 2, 3, 4, 5]))               # 6

Based on this video: Container With Most Water | Two Pointers