Container With Most Water

The problem

Each number in height is the height of a vertical line, and the lines stand one unit apart on a flat floor. Pick two lines. With the floor they form a container, and the water it holds is the distance between the two lines times the height of the shorter one. Return the largest amount of water any two lines can hold. With fewer than two lines, return 0.

What to write

function solve(height: number[]): number

Input
height = [1,8,6,2,5,4,8,3,7]

Output
49

Input
height = [1,1]

Output
1

Constraints

0–10,000 nonnegative integer heights, each ≤ 10,000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 10,000 lines, so measuring every pair is about 50 million areas. Look at what an area depends on: how far apart the two lines are, and the shorter of the two. The taller line adds nothing.

2. Hint 2: Ask a smaller question

   In example 1 the two outermost lines are 1 and 7 tall and 8 apart, so they hold 8. Keep the line of height 1 and give it any other partner. Can that pair ever hold more than 8?

3. Hint 3: Name the pattern

   The answer is a pair of lines, and the widest pair is a natural place to start. Put one pointer at each end and move them toward each other. Every step gives up width, so always leave the line that cannot do better: the shorter one. This is opposing two pointers. Read the lesson on opposing two pointers.

4. Hint 4: State the invariant

   Every pair that uses a line you have already left behind holds no more than an area you have already measured. So the best container is either recorded already or still lies between the two pointers.

5. Hint 5: Sketch the pseudocode

   left = first position, right = last position, best = 0. While left < right: area = (right minus left) × the smaller of the two heights. If area is larger than best, keep it. If the left line is shorter, add 1 to left; otherwise subtract 1 from right. Return best.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Start at both ends and measure the area. Move the shorter line inward, since only finding a taller short boundary can improve on the current pair.

The slow way

Measure the container made by every pair of lines and keep the largest. It is correct, but 10,000 lines make about 50 million pairs, and most of them could have been ruled out without measuring.

The insight

Water rises only to the shorter line. For the two outermost lines, the shorter one already has the farthest partner it will ever get, and no partner can lift the water above its own height. So this is the most it can ever hold, and you can leave it behind.

Step by step

1. Start with the two outermost lines: the widest container. No pair is wider than the first and the last line. From here every move gives up one unit of width, so each move has to be worth it.
2. Measure the water these two lines hold and keep the largest so far. The amount is the distance between the lines times the shorter height, because water would spill over the shorter line. Only the largest amount seen has to be remembered.
3. Move the pointer on the shorter line one step inward. The shorter line limits the water. Any other partner for it is closer and cannot raise the level, so it can never hold more than it does now. On a tie either may go; the code moves the right one.
4. The pointers met: return the largest area seen. Every line that was left behind had already been measured with the best partner it could still get, so no pair that was skipped could have held more.

The same numbered steps are the comments in each solution.

function solve(height) {
  // 1. Start with the two outermost lines: the widest container
  let l = 0,
    r = height.length - 1,
    best = 0;
  while (l < r) {
    // 2. Measure the water these two lines hold and keep the largest so far
    best = Math.max(best, (r - l) * Math.min(height[l], height[r]));
    // 3. Move the pointer on the shorter line one step inward
    if (height[l] < height[r]) l++;
    else r--;
  }
  // 4. The pointers met: return the largest area seen
  return best;
}

function solve(height: number[]): number {
  // 1. Start with the two outermost lines: the widest container
  let l = 0,
    r = height.length - 1,
    best = 0;
  while (l < r) {
    // 2. Measure the water these two lines hold and keep the largest so far
    best = Math.max(best, (r - l) * Math.min(height[l], height[r]));
    // 3. Move the pointer on the shorter line one step inward
    if (height[l] < height[r]) l++;
    else r--;
  }
  // 4. The pointers met: return the largest area seen
  return best;
}

def solve(height):
    # 1. Start with the two outermost lines: the widest container
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        # 2. Measure the water these two lines hold and keep the largest so far
        best = max(best, (right - left) * min(height[left], height[right]))
        # 3. Move the pointer on the shorter line one step inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    # 4. The pointers met: return the largest area seen
    return best

Example 1, traced

Input
height = [1,8,6,2,5,4,8,3,7]

Output
49

Why it works

A line is left behind only when it is no taller than its partner. Every other pair it could still form is narrower and no taller, so none of them holds more than the pair measured in that round. Nothing better is ever thrown away, so the largest area recorded is the largest there is.

Time and space

Time O(n), extra space O(1). Each round measures one pair and moves one pointer one step toward the other, so n lines take fewer than n rounds: O(n) time. Only the two positions and the best area are stored: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Move the shorter line, not the taller one. Moving the taller keeps the low water level and only loses width: on example 1 the answer comes out as 8 instead of 49.
• Move one pointer per round, not both as in Valid Palindrome. Only the shorter line is ruled out; the taller one may still be half of the best pair. Moving both gives 24 on example 1.
• The width is the distance between the two positions, right minus left. Counting the lines from one to the other adds one, and example 2 would give 2 instead of 1.

Pattern

Opposing two pointers. Builds on Two Sum II Input Array Is Sorted.

Keep going