Container With Most Water - Video Solutions

Problem Overview: You get an array height where each value represents the height of a vertical line. Pick two lines that, together with the x-axis, form a container holding the maximum possible water. The container area is determined by the shorter line and the distance between the two indices.

Approach 1: Brute Force (O(n²) time, O(1) space)

The straightforward approach checks every pair of lines. For each pair (i, j), compute the container area using min(height[i], height[j]) * (j - i). Iterate with two nested loops and keep track of the maximum area seen so far. This works because it evaluates all possible containers, guaranteeing the correct result. The downside is the quadratic runtime since there are n(n-1)/2 pairs to examine. This approach mainly helps build intuition for the problem before applying optimizations with techniques like two pointers.

Approach 2: Two Pointers Technique (O(n) time, O(1) space)

The optimal solution uses two pointers starting at opposite ends of the array. One pointer begins at index 0 and the other at n-1. At each step, compute the current area using the width between the pointers and the smaller height. The key insight: the container height is limited by the shorter line, so moving the taller pointer cannot increase the area. Move the pointer pointing to the shorter line inward and recompute the area. This greedy decision removes impossible candidates while still exploring all potentially better containers.

This method works because reducing width is unavoidable when moving pointers, so the only chance to increase area is by finding a taller boundary. By always discarding the shorter wall, the algorithm systematically searches for a better height while keeping the widest possible distance early in the process. The result is a single linear scan of the array using the classic array traversal pattern combined with a greedy elimination strategy.

Recommended for interviews: Interviewers expect the Two Pointers solution. The brute force method shows you understand how the area formula works and can reason about all possibilities. The optimized approach demonstrates pattern recognition and algorithmic efficiency by reducing the search from O(n²) to O(n). Many array optimization problems follow the same pattern of shrinking the search space from both ends.