Recommended resources
The freely available resources this lesson will direct you to.
In our last lesson, you successfully combined sorting with the opposite-end two-pointer technique to solve the 3-Sum problem. We continue our exploration of this powerful pattern today, but with a new twist. We'll be tackling the classic "Container with Most Water" problem.
This problem provides an excellent contrast to 3-Sum. While both use pointers at opposite ends of an array, this problem does not require sorting. Instead, it hinges on a clever greedy strategy to find an optimal solution in a single pass. Mastering this will deepen your understanding of when and how to apply two-pointers to problems that aren't just about finding sums, but about optimizing a geometric or value-based constraint.
Understanding the Problem
The "Container with Most Water" problem asks us to find the maximum area of water that can be contained between two vertical lines on a chart. We are given an array of non-negative integers height, where each integer represents the height of a line at a specific index. The width of the container is the distance between the two lines, and the height is limited by the shorter of the two lines.
The area is calculated as:
Here is an example setup:
A naive approach would be to check every single pair of lines, calculate their area, and keep track of the maximum. This would involve a nested loop, resulting in an O(n²) time complexity. Given your experience, you'll recognize that we can almost always do better when a brute-force solution involves nested loops over a single array.
The O(n) Two-Pointer Solution
The key to an efficient solution is to use the opposite-end two-pointer pattern. We start with the widest possible container by placing one pointer at the beginning of the array (left = 0) and the other at the end (right = n - 1). This guarantees we begin with the maximum possible width.
From this starting position, we calculate the area. Then, we need to decide which pointer to move inward. This is the crucial, greedy decision: we always move the pointer corresponding to the shorter line.
To understand why this works, let's turn to a clear explanation of the core logic.
11. Container With Most Water - In-Depth Explanation
This AlgoMonster article provides a brilliant explanation for the intuition behind the two-pointer strategy.
Please read the section titled Intuition. Focus on the paragraph that begins, "Here's the crucial observation...". The argument presented here is the heart of the algorithm. It explains that if we have height[l] < height[r], moving the right pointer (r) inward can never result in a larger area with the current left pointer, because the width will decrease while the height remains capped by height[l]. Therefore, the only way to potentially find a larger area is to move the left pointer (l) inward, in hopes of finding a line taller than the current height[l].
This greedy choice allows us to systematically discard pairs that cannot possibly form the maximum area, reducing the search space from O(n²) to O(n). At each step, we are essentially eliminating the shorter line as a potential boundary for any future containers with a smaller or equal width.
The process looks like this:
A Detailed Visual Walkthrough
To see this algorithm in action, let's watch a detailed, step-by-step visualization. The following video provides an exceptionally clear blackboard explanation that traces the pointers, calculates the area at each step, and justifies every move.
Two Pointers Pattern: 2/3 (Container With Most Water)
This video by Kantan Coding provides one of the best visual explanations of this problem.
Watch the detailed walkthrough starting from this timestamp. The presenter methodically steps through an example, illustrating: How the width and height are calculated at each iteration. Why the max_area is updated (or not). The decision process for moving either the left or the right pointer. This will solidify the intuition you just read about and prepare you to implement the solution.
From Logic to Code
With a solid conceptual and visual understanding, you're ready to translate this logic into code. The implementation is surprisingly concise. We'll again refer to the AlgoMonster article for its clean presentation.
11. Container With Most Water - In-Depth Explanation
This article breaks down the implementation into clear, manageable steps.
First, read the Solution Approach section. It formalizes the algorithm into a sequence of steps: initialization, the main loop, area calculation, and the pointer-moving logic. Next, study the Python implementation (or your preferred language). Notice how the logic directly maps to what you saw in the video: A while left < right loop. Calculation of current_area. An if/else block that moves left if height[left] is smaller, and right otherwise.
Complexity and Common Pitfalls
Understanding the performance and potential errors is vital for interviews.
- Time Complexity: The solution is O(n). The
leftandrightpointers each traverse the array at most once. - Space Complexity: The solution is O(1). We only use a few variables to store the pointers and the maximum area, requiring constant extra space.
A common point of confusion for those with LeetCode experience is mixing this problem up with "Trapping Rain Water" (LeetCode 42). While both involve vertical lines, their objectives are different. "Container with Most Water" seeks the maximum area formed by just two lines. "Trapping Rain Water" calculates the total volume of water held across the entire landscape, which requires a more complex approach (often involving dynamic programming or two pointers in a different way). Recognizing this distinction is a sign of a sharp problem-solver.
Another pitfall is incorrectly moving the pointers. For instance, moving both pointers when height[left] == height[right]. While moving either pointer is technically correct in this specific case (as the AlgoMonster article points out), the simplest and safest implementation is to just move one, for example, the right one. This avoids potential bugs and keeps the code clean.
Conclusion
In this lesson, you've mastered another application of the opposite-end two-pointer technique. You've seen how a greedy strategy, when correctly applied, can dramatically reduce the complexity of a problem from quadratic to linear time.
Key Takeaways:
- Problem Pattern: "Container with Most Water" is a classic example of optimizing a geometric constraint using two pointers.
- Greedy Strategy: The core insight is to start with maximum width and iteratively move the pointer of the shorter line inward. This works because the shorter line is the bottleneck for the container's height.
- Efficiency: This approach achieves an optimal O(n) time complexity and O(1) space complexity, a massive improvement over the O(n²) brute-force solution.
We have now concluded our deep dive into the two-pointer and sliding window patterns on arrays. In our next module, we will shift our focus to a new data structure: linked lists. You'll see how pointer-based concepts evolve when applied to node-based structures, starting with the powerful "fast and slow pointer" pattern used for cycle detection and finding the middle of a list.