Container With Most Water

Given an integer array height, where height[i] represents the height of a vertical line drawn at index i, find the maximum amount of water that can be contained between any two lines.

The water container is formed by choosing two lines, and the amount of water depends on the shorter line and the distance between the two lines.

Return the maximum water that can be stored.

Brute Force Approach

Any two different lines can form a container. Checking every possible pair guarantees examination of every possible water area.

For selected indices i and j, distance j - i provides container width. The smaller boundary provides water level because water above the shorter line would overflow. Maximum area across all pairs becomes the required answer.

Algorithm

• Return 0 when height contains fewer than two values because container formation requires two boundaries.

• Initialize maxWater with 0 for storing the largest water area found during pair examination.

• Traverse index i from 0 to N - 2 and select height[i] as the left boundary.

• Traverse index j from i + 1 to N - 1 and select height[j] as the right boundary.

• Calculate width as j - i, containerHeight as min(height[i], height[j]), and currentWater as width × containerHeight.

• Update maxWater with the larger value between maxWater and currentWater, then return maxWater after all pairs receive examination.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N²), where N represents the number of lines. Every possible pair of indices may be examined.

Space Complexity: O(1), because only loop indices, area-related variables, and maxWater require auxiliary storage.

Optimal Approach

Start with the two outermost lines because they provide the maximum possible width.

For the current pair, the shorter line limits the container height. If that shorter line is kept and the taller line is moved inward, the width decreases while the limiting height cannot improve, so that choice cannot produce a better area.

Therefore, move the pointer at the shorter line. Although the width becomes smaller, finding a taller boundary is the only way the new container can possibly have a larger area.

This lets us discard one boundary after every comparison and find the answer in a single traversal. This is the standard two-pointer elimination used for the problem

Algorithm

• Return 0 when fewer than two heights are available because a container requires two boundaries.

• Initialize left = 0 and right = N - 1 so the first pair gives the maximum available width. Initialize maxWater = 0.

• While left < right, calculate the current width as right - left and the usable height as min(height[left], height[right]).

• Multiply the width and usable height to obtain the current container area, then update maxWater if this area is larger.

• If height[left] < height[right], increment left because the left boundary is limiting the water height. Otherwise, decrement right because the right boundary is the limiting boundary.

• Continue until the pointers meet, then return maxWater.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N represents the number of lines. At every step, either left moves forward or right moves backward, so each pointer moves at most N positions.

Space Complexity: O(1), because only two pointers and a constant number of area-related variables require auxiliary storage.

FAQs

Q1. Why does the shorter boundary determine the water level?

Water above the shorter boundary would overflow. Therefore, the usable container height is always min(height[left], height[right]).

Q2. Why does the Optimal Approach move the shorter boundary?

Keeping the shorter boundary while reducing the width cannot improve the area because the same short line would continue limiting the height. Moving it is the only choice that may discover a taller limiting boundary.

Q3. Why can the intermediate lines be ignored?

The problem asks us to choose two lines that, together with the x-axis, form the container. Its capacity depends only on the distance between those selected lines and the shorter selected boundary; intermediate lines do not become additional container walls.

Q4. Can both pointers move when both boundary heights are equal?

Yes. Either boundary may be discarded because both currently impose the same limiting height. A standard implementation usually moves one of them to keep the logic simple.

Q5. How should overflow be prevented for large constraints?

Use a sufficiently wide numeric type for width × containerHeight, such as long long in C++ or long in Java, when the constraints can produce values beyond the 32-bit integer range.