17. Container With Most Water

MediumArray Two Pointers Greedy

You are given an array height of n non-negative integers. Picture n vertical walls standing on a flat floor: wall i sits at position i and is height[i] tall.

Choose two walls. Together with the floor they form a container whose water level is limited by the shorter wall, so it holds min(height[i], height[j]) · (j - i) units of water. Return the maximum amount any pair of walls can hold. (The walls in between do not get in the way.)

Example 1

Input: height = [2,7,3,6,4,8,1]
Output: 28

Explanation: Walls at positions 1 and 5 have heights 7 and 8: min(7, 8) · (5 - 1) = 28.

Example 2

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

Example 3

Input: height = [5,1,1,1,5]
Output: 20

Explanation: The two outer walls hold 5 · 4 = 20.

Constraints

2 <= height.length <= 10^5
0 <= height[i] <= 10^4

💡 Hint 1

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

💡 Hint 2

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

💡 Hint 3

So always move the pointer at the shorter wall inward, and keep the best area 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