Container With Most Water — Medium Coding Interview Question

You are given an integer array height of length n. There are 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 a container can store. You may not slant the container.

Example

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

Output: 49

Constraints

• n == height.length
• 2 ≤ n ≤ 10⁵
• 0 ≤ height[i] ≤ 10⁴

Topics & Companies

Topics: arrays, two-pointers, greedy

Asked by: Amazon, Google, Meta, Microsoft, Apple, Bloomberg, Adobe

Optimal Solution Complexity

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

Practice more

• All DSA Problems
• DSA Patterns