Katkat
Back

Find the Container with the Most Water

eBaySoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to optimize an O(n^2) brute-force approach into an O(n) two-pointer solution by leveraging geometric constraints.

Problem Statement

You are given an array of non-negative integers heights where each element heights[i] represents the height of a vertical line at index i on a 2D plane. Two lines, together with the x-axis, form a container that can hold water.

Your task is to write a function that finds two lines such that the container they form, along with the x-axis, holds the maximum amount of water. The area is calculated as: (right_index - left_index) * min(heights[left_index], heights[right_index]).

Note: You may not slant the container.

Function Signature

def max_area(heights: List[int]) -> int:

Constraints

  • n == heights.length
  • 2 <= n <= 10^5
  • 0 <= heights[i] <= 10^4

Examples

Example 1: Input: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 Explanation: The lines at index 1 (height 8) and index 8 (height 7) form an area of (8 - 1) * min(8, 7) = 7 * 7 = 49.

Example 2: Input: heights = [1, 1] Output: 1

Edge Cases

  • Arrays with only two elements.
  • Arrays where all heights are equal.
  • Arrays with zero-height lines.

Hints

Hint 1

A brute-force solution would calculate the area for all possible pairs of lines, resulting in O(n^2) time complexity.

Hint 2

Try using two pointers, one at the beginning and one at the end of the array, to represent the potential walls of the container.

Hint 3

At each step, calculate the area and then move the pointer pointing to the shorter line inward, as moving the taller line inward could never result in a larger area given the narrowing width.

Follow-up questions

  • How would your approach change if you wanted to find the maximum area such that the container must contain at least one line of a specific minimum height?
  • Can you solve this problem if the array is provided as a stream of integers where you don't know the total size in advance?
  • What is the time and space complexity of your solution, and can it be further optimized?