Container With Most Water

Q: What should happen when both lines are the same height?

Moving either one is fine. Any container that keeps one of them is narrower and still capped by that same height, so neither line can do better with a new partner.

Q: Is this the same as the "trapping rain water" problem?

No. Here you pick just two lines and ignore everything between them. Trapping rain water adds up the water held above every position, which needs a different technique.

Q: Why is this asked in infra interviews?

It is less about water and more about proving a greedy step is safe. Being able to argue "this option can never be better, so drop it" is the same reasoning you use when pruning a search over configurations or capacity options.

mediumTwo pointers

You are given a list height of non-negative integers. Each value is a vertical line standing at that position. Pick two lines; together with the ground they form a container. The water it holds is the distance between the two positions times the height of the shorter line. Return the largest amount of water any pair can hold.

Examples

Example 1

Input: height = [2, 5, 4, 1, 6]

Output: 15

Explanation: Lines at positions 1 (height 5) and 4 (height 6): distance 3, shorter height 5, so 3 × 5 = 15.

Example 2

Input: height = [3, 3]

Output: 3

Explanation: Distance 1, shorter height 3.

Hints

Approach

Start with the widest pair, left = 0 and right = n - 1, and narrow it one step at a time, always moving the shorter line.

Compute the area for left and right and update the best.
If height[left] < height[right], move left right. Otherwise move right left.
Repeat until the pointers meet.

Why it is safe: say the left line is shorter. Every other container using that left line is narrower, and its height is still capped by the left line, so none can beat the current one. That line is done and can be dropped. Each step drops one line, so there are n - 1 steps.

ComplexityTime O(n)Space O(1)

Python

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        best = 0
        while left < right:
            area = (right - left) * min(height[left], height[right])
            best = max(best, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return best

Follow-up questions

Return the two positions as well as the area.
Prove, in your own words, that the two-pointer method never skips the best pair.

Frequently asked questions

Moving either one is fine. Any container that keeps one of them is narrower and still capped by that same height, so neither line can do better with a new partner.

No. Here you pick just two lines and ignore everything between them. Trapping rain water adds up the water held above every position, which needs a different technique.

It is less about water and more about proving a greedy step is safe. Being able to argue "this option can never be better, so drop it" is the same reasoning you use when pruning a search over configurations or capacity options.

Problem statement