Container With Most Water

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

Solution

We will implement this question using opposite two-pointers with the following steps.

  1. Initialize left and right pointer to 0 and len(height)-1. Initialize max_area = 0.
  2. Perform two pointers selections (steps 3-4) while left < right.
  3. The max_area is the maximum of the current max_area and (right - left) * min(height[left], height[right])
  4. Update left += 1 if height[left] < height[right], else right -= 1.
  5. Return the final max_area.

The logic behind this two pointers algorithm is that we start from the two ends and work our way into the middle. Given two vertical lines, the area of that container is (right - left) * min(height[left], height[right]). So the only way we can hold more water when the horizontal distance between two pointers decrease, is to increase the vertical distance min(height[left], height[right]). We wish to keep the taller line from height[left], height[right] and continue searching for another line that's taller than the lower line, which potentially forms a larger container.

Implementation

1def maxArea(self, height: List[int]) -> int:
2    left, right = 0, len(height) - 1
3    max_area = 0
4    while left < right:
5        max_area = max(max_area, (right - left) * min(height[left], height[right]))
6        if height[left] < height[right]:
7            left += 1
8        else:
9            right -= 1
10    return max_area
Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Not Sure What to Study? Take the 2-min Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫