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 \frac{n(n-1)}{2} comparisons. This gives a time complexity of O(n²). For large n (e.g., 100k), this is not feasible. The space complexity is O(1) (constant extra space), since we only use a few variables to track indices and area.

• Two-Pointer Approach: We traverse the array with two pointers, each moving at most n steps in total. Thus the time complexity is O(n). We do a constant amount of work in each step (a few calculations and comparisons). The space complexity is O(1) as well, using only a fixed number of extra variables (pointers and area trackers).

In summary, the two-pointer approach is dramatically more efficient, turning a quadratic time solution into linear time, which is crucial given the problem constraints.

Common Mistakes

• Using the larger height instead of the smaller: A frequent mistake is to calculate area using the larger of the two heights. Remember that the water contained is limited by the shorter line. Using the taller line for height will overestimate the area. Always use min(height[i], height[j]) in the formula.

• Off-by-one errors in width calculation: Ensure that the width is computed as j - i (if using 0-based indices). If using 1-based indexing for positions, the distance would be (j - i), but pay attention to index differences. For example, between index 1 and 8 (0-based) there are 7 intervals, which correctly equals 8 - 1. Using j - i - 1 or similar adjustments incorrectly will miscalculate the width.

• Not moving the correct pointer: In the two-pointer method, moving the wrong pointer can lead to missing the optimal solution. A common error is moving the pointer with the greater height, which can cause you to skip valid solutions. Always move the pointer at the shorter line inward (if heights are equal, moving either pointer by one is fine).

• Inefficient early break logic: Some might try to break out of the loop early if heights are in a certain order. Be careful – the two-pointer algorithm should continue until the pointers meet to ensure all candidate pairs are evaluated. Breaking out early (except when l >= r) could miss the true maximum.

• Mis-initializing max area: Initialize maxArea to 0 (since area cannot be negative). Forgetting to initialize, or using a very large negative number unnecessarily, can cause issues. Given all heights are non-negative, 0 is a safe starting value (and also covers the case where no water can be trapped, though here with n>=2 and heights>=0, minimum area is 0).

• Not considering all pairs in brute force: If implementing brute force, make sure to loop j from i+1 (not i) to avoid pairing a line with itself (which doesn't form a container and area would be 0). Also ensure you check all pairs; sometimes new programmers accidentally limit the inner loop incorrectly or skip some pairs.

Edge Cases

• Minimum Input (n=2): With just two lines, the result is simply the area between those two lines (min(height[0], height[1]) * 1). Both approaches handle this naturally (the loop runs once in two-pointer, or one pair in brute force). Example: [3, 7] should return area = 3 * 1 = 3 if those are the only two heights.

• All Zero Heights: If all lines have height 0, no water can be contained. The output should be 0. Both approaches will handle this: brute force will calculate 0 for every pair, and two-pointer will likewise find only 0 areas and thus return 0.

• One Line Significantly Taller: If one line is extremely tall compared to others, the max area might involve that tall line and another line far away to get large width. Example: [1, 1000, 2, 1000, 1] – the maximum area here is 1000 (min(1000,1000) * distance 1 if the two tall lines are adjacent) or perhaps a tall with a farther smaller line? Actually check: min(1000,1000)*3 = 3000 if we take the two 1000s with distance 3 (they are at indices 1 and 3), so that's larger. The two-pointer method correctly finds such cases. The edge scenario to note is that the tallest two lines are often a good candidate, but if they are not the farthest apart, sometimes a slightly shorter line farther apart wins. Ensure your solution checks all possibilities via the two-pointer sweep.

• Multiple Lines of Same Height: If the array has many equal heights (e.g., all elements are 5, or a long plateau of the same height), the best container will be the two farthest lines. The two-pointer approach will find it: starting at the ends (both height 5, width n-1, area = 5*(n-1)), then as it moves inward the width shrinks. The first area computed is actually the maximum in such a case. Make sure your algorithm doesn't prematurely stop on equal heights. (In the two-pointer approach, when heights are equal, we arbitrarily move one pointer – this is fine since both sides are equivalent in height.)

• Very Large n: While not a "case" in terms of input values, it's worth noting performance on the upper constraint. For n=100,000, brute force would never finish in reasonable time. The two-pointer will handle it in linear time. So the edge consideration is ensuring to use the two-pointer approach for large inputs.

• No Slanting Constraint: Although the problem explicitly says you cannot slant the container, some might imagine diagonal placement. This is just a reminder that the container’s sides are vertical lines at the chosen indices. So only vertical heights matter, and you don’t consider any angle – essentially there’s no trick beyond using vertical lines.

Alternative Variations

• Uneven Spacing Between Lines: In the classic problem, lines are at positions 0, 1, 2, ..., n-1 (equally spaced by 1). A variation could be if the lines are at arbitrary x-coordinates (for example, you have pairs of coordinates (x, height)). The problem then asks for the two lines that form the biggest container, where the width is the difference in their x-coordinates. The solution approach is essentially the same two-pointer strategy — you would sort lines by their x-coordinate and then use a two-pointer-like sweep considering width as x[j] - x[i]. The main change is computing width using given coordinates instead of index difference.

• Circular Arrangement: Imagine the vertical lines are placed around a circle (at equally spaced angles). If we wanted to find two lines on a circle that can hold the most water (with the "width" being the smaller arc distance between them along the circle), this becomes a bit more complex because the container could wrap around the end to the beginning. This variant would require checking pairs in a circular manner. One approach is to duplicate the array (simulate two cycles) and use a similar two-pointer technique within a sliding window of length n. This is a more advanced variation and not as commonly asked, but it’s conceptually related in maximizing area between lines.

• K-Container Problem: A theoretical extension: choose k lines that form a closed shape with the x-axis to maximize contained area. For example, with 3 lines you’d form a triangle-like container (though the problem constraints usually define only two vertical sides with the x-axis as base). This is not a standard problem, but thinking about more than two lines could lead to different interpretations (it often turns into a different problem entirely, so it's more of a thought experiment than a known interview question).

• Trapping Rain Water: While not a direct variation in terms of selecting two lines, the famous Trapping Rain Water problem is related. Instead of just two lines forming a container, every adjacent pair of lines can trap water above the shorter one, and you sum up all trapped water between all lines. The approach to solve that is different (dynamic programming or two-pointer in a different way), but it's a variation of the "water between lines" concept.

Related Problems for Further Practice

Practicing similar problems can reinforce the understanding of two-pointer techniques and area calculation logic:

• Trapping Rain Water (LeetCode 42) – Calculate how much water is trapped between elevation maps (heights). This involves multiple containers formed between many lines and requires a different strategy (but also uses the concept of min of left/right bounds).

• Largest Rectangle in Histogram (LeetCode 84) – Find the largest area rectangle that can be formed in a histogram. This is a different scenario (contiguous bars forming a rectangle), solved using a stack, but it also deals with maximizing area under height constraints.

• 3Sum (Three Numbers Sum to Zero, LeetCode 15) – While a different problem (finding three numbers that sum to zero), it utilizes the two-pointer approach after sorting the array. It's good practice for the two-pointer technique in a different context.

• Two Sum II – Input Array Is Sorted (LeetCode 167) – Find two numbers in a sorted array that add up to a target. This is a classic two-pointer problem where you move pointers based on sum comparisons. It helps solidify the idea of moving pointers inward for optimization.

• Pair with Given Sum (Two-pointer variation) – More generally, any problem where you need to find two indices or elements that meet a certain condition (sum, difference, product) and the array can be sorted, is a good practice for two-pointer approach. Examples include two-sum problems, pair with difference k, etc.

Each of these problems will help you get comfortable with the thought process of the two-pointer pattern and other techniques for optimizing brute force searches.