Container With Most Water

Learning goal: Translate the container definition into an area formula and identify what must be optimized.

Core idea Two chosen indices form a container whose width is their distance. Its usable height is limited by the shorter line, so the area is min(height[left], height[right]) * (right - left). We need the largest value over all valid pairs without spending quadratic time.

Algorithm plan

• Consider two indices, left and right.
• Compute the current area using the shorter wall.
• Record the largest area seen so far.
• Shrink the interval according to the shorter wall.

Micro-example For heights [1,8,6,2,5,4,8,3,7], indices 1 and 8 give width 7 and limiting height 7, so the area is 49.

Pitfalls

• The taller wall does not determine the filled height.
• Width is right - left, not right - left + 1.
• The goal is a maximum area, not the tallest pair.

Recap

• Area combines width and the shorter height.
• The optimal algorithm must avoid checking every pair.
• The widest initial pair gives a useful starting bound.

Learning goal: Understand why moving the shorter pointer is the only greedy move that can help.

Core idea Begin with the widest possible container: left = 0 and right = n - 1. Moving either pointer inward strictly decreases width. If the shorter wall stays, the new area cannot exceed the old area because the width is smaller while the limiting height is no larger. Therefore, the only potentially productive move is to discard the shorter wall and search for a taller replacement.

Algorithm plan

• Compute the area for the current pair.
• Update best with the larger area.
• If height[left] < height[right], increment left.
• Otherwise, decrement right.
• Continue until the pointers meet.

Micro-example With heights 8 and 7, the right wall is shorter. Moving the left wall keeps height at most 7 and reduces width, so move right instead.

Pitfalls

• Do not move the taller wall just because it looks like the stronger candidate.
• Equal heights permit moving either pointer; one move is enough.
• Always update the area before moving a pointer.

Recap

• Width decreases on every move.
• Only replacing the shorter wall can raise the limiting height.
• This greedy rule eliminates impossible pairs safely.

Learning goal: Turn the greedy observation into a complete one-pass algorithm.

Core idea The two pointers maintain a shrinking interval of candidate walls. At each interval, we evaluate its area and permanently discard the shorter endpoint. This is safe because every container using that endpoint with a future, closer pointer has smaller width and cannot have a larger limiting height unless that endpoint is replaced.

Algorithm plan

1. Set left = 0, right = n - 1, and best = 0.
2. While left < right, compute width and the shorter height.
3. Update best with the current area.
4. Move the pointer at the shorter wall inward.
5. Return best.

while left < right:
    best = max(best, min(height[left], height[right]) * (right - left))
    if height[left] < height[right]:
        left += 1
    else:
        right -= 1

Micro-example The first pair in the walkthrough has area 8. Moving left reaches heights 8 and 7, producing 49, the best answer.

Pitfalls

• Brute force checks O(n²) pairs and is too slow at the maximum input size.
• Moving the taller pointer breaks the greedy justification.
• The loop must stop when left and right meet.

Recap

• Evaluate, update, then move the shorter pointer.
• Each iteration removes one endpoint from consideration.
• The result is computed in one linear scan.

Learning goal: Trace every pointer decision on a concrete input and verify the final maximum.

Core idea Use height = [1,8,6,2,5,4,8,3,7]. The pointers begin at indices 0 and 8, giving the maximum possible width. Each row computes the current area, keeps the best result, and moves only the shorter wall.

Pointer movement

Micro-example At indices 1 and 8, the area is min(8,7) * 7 = 49. Later pairs are narrower, and none exceeds this value.

Pitfalls

• A lower current area does not replace best.
• Equal-height walls still require one pointer to move.
• A pointer move changes the next width, so recompute area each time.

Recap

• The best value becomes 49 at (1, 8).
• The scan ends when only one position remains between the pointers.
• The widget shows why every move follows the shorter wall.

Learning goal: Recognize the tempting mistakes that invalidate or slow down this solution.

Core idea The greedy rule is precise: after measuring a pair, move the shorter wall. Moving the taller line cannot increase the limiting height because the shorter line remains, while the width decreases. A brute-force solution may produce correct answers, but it examines every pair and costs O(n²) time.

Edge cases

• With exactly two heights, return their product because the width is 1.
• Heights of 0 produce area 0 unless another pair is available.
• Equal walls are safe: move either pointer after measuring.
• Very large arrays require the linear-time scan.

Micro-example For [1,1], the only area is 1. For [5,5,5], the first pair gives 10; after one move, the remaining width is smaller, so the maximum stays 10.

Pitfalls

• Moving the taller line: this shrinks width while leaving the bottleneck unchanged.
• Brute-forcing all pairs: O(n²) comparisons violate the intended scalability.
• Using max(height[left], height[right]) instead of min(...) overestimates capacity.
• Forgetting to measure the current pair before moving loses candidates.

Recap

• Shorter-wall movement is both the optimization and the proof.
• Handle equal heights and zero heights naturally.
• Check the current area before every pointer move.

Learning goal: Justify the efficiency of the two-pointer solution and retain its reusable pattern.

Core idea Each iteration moves either left forward or right backward, and neither pointer ever reverses direction. Across the entire scan, there are at most n - 1 moves. The algorithm stores only a few variables, so its auxiliary space remains constant.

Algorithm plan

• Initialize pointers at opposite ends.
• Measure the current container.
• Update the maximum.
• Move the shorter wall inward.
• Stop when the pointers meet.

Micro-example For n = 9, the walkthrough performs only pointer moves across the interval, rather than checking all 9 × 8 / 2 = 36 pairs.

Pitfalls

• Calling the method O(1) because it uses two variables ignores the loop; time is O(n).
• Counting the input array as auxiliary memory is unnecessary; the algorithm does not copy it.
• A correct complexity claim still requires the correct shorter-wall rule.

Recap

• Time complexity: O(n).
• Extra space complexity: O(1).
• General pattern: when width shrinks and one boundary limits value, replace the limiting boundary.