Solving “Container With Most Water” Coding Interview Problem

Problem Statement

Given an array of integers, where each integer represents the height of a vertical line on a chart, determine the two lines which, together with the x-axis, forms a container that can hold the most water. The objective is to maximize the area of the container.

Note: The width of the container is the difference between the indices of the two lines.

Example

Given the array [1, 8, 6, 2, 5, 4, 8, 3, 7], the maximum area is formed between the lines at positions 2 (height 8) and 9 (height 7), which gives an area of 49.

Intuition

Imagine you have a chart with vertical bars of varying heights. The question essentially asks which two bars, when connected at the top by a horizontal line, enclose the largest area with the x-axis.

Brute Force Solution

A brute force approach involves checking the area between every pair of lines. Iterate through every pair of lines and calculate the area. Keep track of the maximum area encountered.

public class Container {
    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxAreaBruteForce(height)); // Output should be 49
    }

    public static int maxAreaBruteForce(int[] height) {
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int minHt = Math.min(height[i], height[j]);
                maxArea = Math.max(maxArea, minHt * (j - i));
            }
        }
        return maxArea;
    }
}

The brute force solution has a time complexity of O(n²) because it checks all possible pairs of lines.

Optimal Solution

Instead of examining all pairs of lines, we can use the two-pointer approach.

Start with pointers at the two ends of the array. Move the pointer pointing to the shorter line towards the other, hoping to find a taller line and thus a larger container.

Illustration

Using the array[1, 8, 6, 2, 5, 4, 8, 3, 7] as an example, start with pointers at positions 1 (height 1) and 9 (height 7). The current container’s height is determined by the shorter line, i.e., height 1. To try and find a bigger container, move the pointer at position 1 to the next position.

Repeat this until the pointers meet.

public class Container {

    public static int maxAreaOptimal(int[] height) {
        int maxArea = 0, left = 0, right = height.length - 1;
        while (left < right) {
            int minHt = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, minHt * (right - left));
            
            // Move the pointer pointing to the shorter line
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

This optimal solution has a time complexity of O(n) since each pointer only moves across the array once.

The two-pointer approach drastically reduces the number of pairings to be checked compared to the brute force method. Instead of checking every possible pair (which is O(n²)), the two-pointer technique checks each pairing once, resulting in a linear time complexity of O(n).