NeetCode 150: Container With Most Water

Table of contents

The Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

A Visual Example

Image taken from LeetCode.

The Approach

The goal is to maximize the area, similar to #84 Largest Rectangle in Histogram, but the difference here is that it is between two vertical lines. We should not sort heights as the order of the lines matter, the difference in their positions determines the length of the container.

As such, we can employ the Two Pointer method & traverse heights from opposite ends of the array, finding the area between any two lines.

If the left line has a greater height than the right, move the right pointer backwards (not fowards to prevent it from accessing an invalid index), as the left line is currently maximized. Apply the opposite for the case where the right is greater than the left.

If both the left & right heights are equal, move both pointers fowards & backwards respectively to “reset” this consideration.

My Solution

class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int maxWater = 0;

        // Place the left & right pointers at each edge of heights. Calculate currentMaxWater
        // & compare it to maxWater (update it if greater). There are 3 outcomes 
        // for moving l & r;
        // 1) If leftmostHeight == rightmostHeight: move l & r (move comparisons foward).
        // 2) If leftmostHeight > rightmostHeight: move r (need greater value for right side).
        // 3) If leftmostHeight < rightmostHeight: move l (need greater value for left side).
        while (l < r) {
            int leftmostHeight = height[l];
            int rightmostHeight = height[r];
            int currentMaxWater = getSmallerValue(leftmostHeight, rightmostHeight) * (r - l);
            maxWater = getGreaterValue(currentMaxWater, maxWater);
            
            if (leftmostHeight == rightmostHeight) {
                l++;
                r--;
            } else if (leftmostHeight > rightmostHeight) {
                r--;
            } else {
                l++;
            }
        }
        return maxWater;
    }

    // Returns the greater value.
    private int getGreaterValue(int a, int b) {
        if (a > b) {
            return a;
        } else {
            return b;
        }
    }
    // Returns the smaller value.
    private int getSmallerValue(int a, int b) {
        if (a < b) {
            return a;
        } else {
            return b;
        }
    }
}

We first initialize the left & right pointers at the opposite ends of the array, l & r respectively. maxWater, which keeps track of the max value seen so far is also initialized to 0.

Until both pointers cross (checked using the while loop), find currentMaxWater where the height is the height of the smaller line & the length is the difference between their index values. maxWater is updated if currentMaxWater > maxWater.

There are 3 scenarios in moving the pointers:

• If leftmostHeight == rightmostHeight: move l & r (move comparisons foward).
• If leftmostHeight > rightmostHeight: move r (need greater value for right side).
• If leftmostHeight < rightmostHeight: move l (need greater value for left side).

getGreaterValue() & getSmallerValue() are methods that return the greater or smaller value respectively.

At the end, return maxWater.