Container With Most Water

Container With Most Water is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Converging (Sorted Array Target Sum) subpattern.

Problem statement

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.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1] Output: 1

Constraints:

- n == height.length

- 2 <= n <= 105

- 0 <= height[i] <= 104

Topics and companies

Topics: Array, Two Pointers, Greedy.

Reported in interviews at Amazon, Google, Microsoft, Facebook, Goldman Sachs, Adobe, Apple.

How to practise Container With Most Water on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Container With Most Water in the code editor, or read the Container With Most Water editorial for a worked solution with its approach and complexity analysis.

Where Container With Most Water sits in the DSA pattern sheet

• Two Pointers pattern guide
• Converging (Sorted Array Target Sum) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Container With Most Water

Other problems that use the same Converging (Sorted Array Target Sum) and Two Pointers techniques:

• Boats to Save People — Medium, same subpattern
• 4Sum — Medium, same subpattern
• Squares of a Sorted Array — Easy, same subpattern
• 3Sum Closest — Medium, same subpattern
• 3Sum Smaller — Medium, same subpattern
• 3Sum — Medium, same subpattern