DSA With AI
Week 1 ยท Two Pointers

Container With Most Water

Given vertical line heights, choose two lines that maximize width times the shorter height.

Medium Two Pointers Week 1 Practice runner

Frame the problem

  • Area is limited by the shorter wall.
  • Width shrinks as pointers move inward.
  • The optimal pair is not necessarily the two tallest walls.
1. Reveal example inputs and outputs

Example 1

Input:

max_area([
  1,
  8,
  6,
  2,
  5,
  4,
  8,
  3,
  7
])

Output:

49

Example 2

Input:

max_area([
  1,
  1
])

Output:

1
2. Brute force first

What would checking every pair cost? Which pointer move can discard many pairs at once?

3. Reveal the insight ladder
  1. Start with the widest possible container.
  2. Compute area using the shorter wall.
  3. Move the pointer at the shorter wall inward.
  4. A taller partner with less width is the only way to improve after discarding that shorter wall.
4. Dry run before code
  1. height = [1,8,6,2,5,4,8,3,7].
  2. Start at 1 and 7 for area 8.
  3. Move off height 1; later 8 and 7 at width 7 gives area 49, the best.
5. Reveal final Python solution 
def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        best = max(best, (right - left) * min(height[left], height[right]))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Complexity: Time O(n), space O(1).

Interview narration

  • The proof is about safely discarding the shorter wall.
  • Keeping the shorter wall while reducing width cannot improve area with that same limiting height.
  • So I move the shorter side and preserve the only possible path to a larger area.

Common traps

  • Moving the taller wall first.
  • Using max height instead of min height for area.
  • Assuming adjacent bars matter like the trapping-rain-water problem.

Follow-up drills

1. Why is moving the shorter wall safe?

Any container using that same shorter wall with a smaller width cannot exceed the current area unless the limiting height increases, which requires moving away from the shorter wall.

2. How is this different from Trapping Rain Water?

Container With Most Water chooses one pair of boundaries. Trapping Rain Water aggregates water across many positions, so the state and proof differ.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.