Container With Most Water

MediumArray Two Pointers Greedy

A garden designer has a row of upright stone slabs, one metre apart: slab i stands at position i and is height[i] units tall. They want to pick two slabs and flood the ground between them to make a small pond.

The water can only rise as high as the shorter of the two chosen slabs, and the slabs in between do not block anything. So slabs i < j hold min(height[i], height[j]) · (j - i) units of water. Return the largest amount any pair of slabs can hold.

Example 1

Input: height = [3,9,4,8,2,5]
Output: 20

Explanation: Slabs 1 and 5 have heights 9 and 5: min(9, 5) · (5 - 1) = 20. The two tallest slabs, 1 and 3, hold only 8 · 2 = 16.

Example 2

Input: height = [6,1,6]
Output: 12

Explanation: The short middle slab does not matter: the outer slabs hold 6 · 2 = 12.

Example 3

Input: height = [1,2,4,3]
Output: 4

Explanation: The widest pair is capped at height 1. Slabs 1 and 3 do better with min(2, 3) · 2 = 4.

Constraints

There are between 2 and 10^5 slabs.
Each slab is between 0 and 10^4 units tall.

💡 Hint 1

Trying all pairs is O(n²). Start with the widest possible pond: the first and last slabs.

💡 Hint 2

Moving the taller slab inward can never help: the width shrinks and the water level is still capped by the shorter slab.

💡 Hint 3

So always move the pointer at the shorter slab inward, and keep the best amount seen.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Start with two pointers at the two ends, the widest container. Its area is limited by the shorter wall. Any other container that keeps that shorter wall is narrower and cannot be taller, so the shorter wall can be discarded: move its pointer inward. Repeat, recording the best area, until the pointers meet. Each step discards one wall, so the scan is linear.

Time O(n)Space O(1)

function maxArea(height) {
  let lo = 0;
  let hi = height.length - 1;
  let best = 0;
  while (lo < hi) {
    best = Math.max(best, Math.min(height[lo], height[hi]) * (hi - lo));
    if (height[lo] < height[hi]) lo++;
    else hi--;
  }
  return best;
}

class Solution {
    public int maxArea(int[] height) {
        int lo = 0, hi = height.length - 1, best = 0;
        while (lo < hi) {
            best = Math.max(best, Math.min(height[lo], height[hi]) * (hi - lo));
            if (height[lo] < height[hi]) lo++;
            else hi--;
        }
        return best;
    }
}

/**
 * @param {number[]} height
 * @return {number}
 */
function maxArea(height) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit