Crack the Backend

Problem Statement

You are given n non-negative integers height[i] representing n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container that holds the most water. Return the maximum amount of water the container can store.

The container is formed by two lines and the x-axis; its width is the distance between the two indices, and its height is the minimum of the two line heights. So area = (right - left) × min(height[left], height[right]).
We cannot slant the container; the water level is determined by the shorter of the two lines.

Key Observations

The area is (right - left) * min(height[left], height[right]). To maximize, we start with the widest pair (left=0, right=n-1) and then move the pointer at the shorter line inward. Why? Because the current area is limited by the shorter line; moving the longer one inward only reduces width and cannot increase the minimum height, so the area can only decrease. Moving the shorter one might let us find a taller line and possibly a larger area.
So we use two pointers at the ends; at each step compute the area, update the maximum, then move the pointer at the smaller height inward. O(n).

Approach

High-level: Two pointers left=0, right=n-1. While left < right: compute area (right-left)*min(height[left], height[right]), update best. If height[left] < height[right], left++; else right--. Return best.

Steps:

left = 0, right = height.length - 1, best = 0.
While left < right: best = max(best, (right - left) * min(height[left], height[right])). If height[left] < height[right], left++; else right--.
Return best.

Implementation

Java

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1, best = 0;

    while (left < right) {
        best = Math.max(best, (right - left) * Math.min(height[left], height[right]));

        if (height[left] < height[right]) {
            left++;
        }
        else {
            right--;
        }
    }

    return best;
}

Test Cases

Example 1

Input

height = [1,8,6,2,5,4,8,3,7]

Expected

49

Explanation

Lines at index 1 and 8.

Complexity Analysis

Time: O(n).
Space: O(1).

Follow-ups

Trapping Rain Water: 2D version with elevation map.