Leetcode 11. Container With Most Water

Clarification

Okay, so first I’ll restate the problem to make sure I understand it correctly. We are given an integer array height, where each element represents a vertical line. We need to choose two lines that, together with the x-axis, form a container that can hold the most water.

The amount of water between two lines is: width * min(left height, right height). So the shorter line limits the water level.

Example.

Are all heights non-negative integers?
Can I assume the array has at least two elements?
Should I return only the maximum area, not the indices?

Brute-force Approach

The simple way is to brute force every pair of lines. For each pair, calculate the area and keep the maximum. That would work, but there are n² pairs, so the time complexity is O(n²).

Optimized Approach

The optimized approach is two pointers, in particular left and right pointers. What I’ll do is to put left pointer at the beginning and right at the end: At each step, I calculate the area between them. Then the key idea is: move the pointer with the shorter height inward.

Why? At each step, the width is already the largest possible for those two pointers. Since the area is limited by the shorter line, keeping that shorter line while moving the taller line inward cannot improve the height limit, and the width only decreases. So the only meaningful chance to improve the area is to move the shorter side. So I always try to replace the shorter line with a potentially taller one and keep track of the maximum. We can stop when the two pointers meet.

Example.

The time complexity is O(n), the space is O(1).

Code

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

Follow-up