11. Container With Most Water - Detailed Explanation

Java implementation (brute force):

Java implementation (two-pointer):

Complexity analysis

• Brute force approach: The brute force solution checks every pair of indices (i, j), which is on the order of n(n-1)/2 comparisons. That gives a time complexity of O(n²). For large n, say 100k, it is not feasible. The space complexity is O(1), constant extra space, since it tracks only a few indices and the running area.

• Two-pointer approach: The two pointers traverse the array, each moving at most n steps in total. The time complexity is therefore O(n). Each step performs a constant amount of work, a few calculations and comparisons. The space complexity is O(1) as well, using a fixed number of extra variables such as the pointers and the area tracker.

In summary, the two-pointer approach turns a quadratic solution into a linear one. Given the problem constraints, that difference decides whether your submission finishes at all.

Common mistakes

• Using the larger height instead of the smaller: A frequent mistake is to compute the area from the taller of the two lines. The water is limited by the shorter line. Using the taller line overestimates the area. Always put min(height[i], height[j]) in the formula.

• Off-by-one errors in the width: With indices counted from zero, the width is j - i. Between index 1 and index 8 there are 7 intervals, which is exactly 8 - 1. Writing j - i - 1 or a similar adjustment miscalculates the width.

• Moving the wrong pointer: In the two-pointer method, moving the pointer at the greater height can skip the optimal pair. Always move the pointer at the shorter line inward. When the two heights are equal, moving either pointer by one is fine.

• Breaking out of the loop early: Some candidates add a shortcut that exits once the heights fall into a certain order. Be careful here. The sweep has to continue until the pointers meet, so that every candidate pair is evaluated. Any early exit other than l >= r can miss the true maximum.

• Mis-initializing the maximum: Initialize maxArea to 0, since an area cannot be negative. Leaving it uninitialized, or starting from a large negative number, invites trouble for no benefit. All heights are non-negative and n >= 2, so 0 is a safe starting value, and it also covers the case where no water can be trapped.

• Skipping pairs in brute force: If you write the brute force version, loop j from i+1, not from i. Pairing a line with itself does not form a container, and its area is 0. Check that the inner loop bound really covers every remaining line, since a mistyped limit silently drops valid pairs.

Edge cases

• Minimum input (n=2): With two lines the answer is simply the area between them, min(height[0], height[1]) * 1. Both approaches handle it naturally. The two-pointer loop runs once, and brute force evaluates one pair. For [3, 7] the area is 3 * 1 = 3.

• All zero heights: If every line has height 0, no water can be contained and the output is 0. Brute force computes 0 for every pair. The two-pointer sweep likewise finds only zero areas and returns 0.

• One line significantly taller: When one line is extremely tall compared to the others, the maximum area may pair it with a line far away to gain width. Take [1, 1000, 2, 1000, 1]. The two lines of height 1000 sit at indices 1 and 3, giving min(1000,1000) * 2 = 2000, which exceeds any pairing of a tall line with a short one. The two-pointer method finds such cases correctly. The scenario to remember is this: the two tallest lines are often a good candidate, but not when they stand close together. A slightly shorter line much farther away sometimes wins, and the two-pointer sweep weighs both.

• Multiple lines of the same height: If the array holds many equal heights, for instance all 5s or a long plateau, the best container is the two farthest lines. The two-pointer approach finds it at once. Starting at the ends gives height 5 and width n-1, for an area of 5 * (n-1), and the width only shrinks as the pointers move inward. The first area computed is the maximum in such a case. Make sure your loop does not stop early on equal heights. When the two heights match, the approach moves one pointer arbitrarily, which is safe because both sides cap the area at the same value.

• Very large n: This is a performance note rather than a case in terms of input values. At n = 100,000 brute force will never finish in reasonable time, while the two-pointer sweep handles it in linear time. The edge consideration is to pick the linear approach for large inputs.

• No slanting constraint: The problem says explicitly that you cannot slant the container, yet some readers still picture a diagonal placement. The sides are vertical lines at the chosen indices. Only vertical heights matter, and no angle enters the calculation.

Alternative variations

• Uneven spacing between lines: In the classic question the lines sit at positions 0, 1, 2, ..., n-1, spaced one apart. A variation gives arbitrary x-coordinates, as pairs (x, height), and asks for the two lines that form the biggest container. The width is then the difference of the x-coordinates. The strategy barely changes. Sort the lines by x-coordinate and run the same inward sweep, computing the width as x[j] - x[i].

• Circular arrangement: Suppose the vertical lines sit around a circle at equally spaced angles, and the width between two lines is the smaller arc distance along the circle. This version is harder, because a container can wrap from the end of the array back to the beginning. One approach duplicates the array to simulate two cycles, then applies a two-pointer technique inside a sliding window of length n. It is an advanced variation and rarely asked, though it is conceptually related.

• K-container problem: A theoretical extension picks k lines that close a shape with the x-axis and asks you to maximize the contained area. With three lines you would form something like a triangle, though the standard constraints define only two vertical sides over the x-axis base. This is not a standard problem. Allowing more than two lines usually turns into a different problem, so treat it as a thought experiment rather than a known interview question.

• Trapping Rain Water: The well known Trapping Rain Water problem is related, though it is not a variation on selecting two lines. There, every dip between lines traps water above the shorter neighbor, and you sum all the water across the whole array. The solution uses dynamic programming or a different form of two pointers, but it builds on the same idea of water between lines.

Related problems for further practice

Practicing similar problems reinforces both the two pointers technique and the area calculation logic.

• Trapping Rain Water (LeetCode 42): Calculate how much water an elevation map traps. It involves many containers at once and needs a different strategy, though it also turns on the minimum of the left and right bounds.

• Largest Rectangle in Histogram (LeetCode 84): Find the largest rectangle that fits inside a histogram. Contiguous bars form the rectangle and a stack solves it, but it is another maximization under height constraints.

• 3Sum (LeetCode 15): Find three numbers that sum to zero. It applies two pointers after sorting the array, which is the same technique in a different setting.

• Two Sum II, input array is sorted (LeetCode 167): Find two numbers in a sorted array that add up to a target. The pointers move based on how the current sum compares with the target. It solidifies the idea of moving pointers inward.

• Move Zeroes: The answer page for Move Zeroes uses two indices that travel in the same direction rather than toward each other, which is the other half of this pattern.

• Is Subsequence: The Is Subsequence write-up walks one pointer per string, a useful contrast with the single-array sweep here.

Each of these problems builds the judgment to see when a brute force search over pairs can collapse into a single linear scan.