MEDIUM

DATA STRUCTURES AND ALGORITHMS

GRAPH THEORYARRAYSSEARCHSORTING

Written By

Tom Wagner

Carlos Wang

Introduction Container With Most Water

The Container with Most Water problem involves finding the largest possible area that can be formed by two vertical lines on a graph, bounded by the height of the shorter of the two lines. This problem can be solved using a two-pointer approach, which involves traversing the array from both sides and keeping track of the maximum area found so far.

Problem Container With Most Water

Given `n`

non-negative integers `a0, a1, a2, ..., a[n-1]`

, where each represents a point at coordinate `(i, a[i])`

, `n`

vertical lines are drawn such that the two endpoints of the line `i`

is at `(i, 0)`

and `(i, ai)`

. Find two lines that, together with the x-axis, form a container that can hold the most amount of water possible.

**Input:**`heights`

= [3, 9, 4, 8, 2, 6, 1]**Output:**24

**Constraints**

- number of integers n: [2, 10,000]
- each integer a[i]: [0, 1,000]

Solution Container With Most Water

Watch Someone Solve Container With Most Water

FAANG InterviewPython Interview

Advance this person to the next round?

Technical Skills:

4/4

Problem Solving Ability:

4/4

Communication Ability:

4/4

Show Transcript

Watch more mock interviews

In the context of this problem, the size of the 2D container is determined by multiplying its width by its height. The brute force approach is to calculate all possible containers to find the largest one.

To accomplish this, we can iterate over the heights, forming a container with every other height to its right. Each container's size will be the lower of the two heights multiplied by the distance between the heights.

We can track the max container size as we go and return the max container size at the end of our iteration.'

```
def max_water(heights: list[int]) -> int:
ln = len(heights)
max_area = 0
for left_index in range(ln):
left_height = heights[left_index]
for right_index in range(left_index + 1, ln):
right_height = heights[right_index]
width = right_index - left_index
height = min(left_height, right_height)
area = width * height
max_area = max(area, max_area)
return max_area
```

```
1def max_water(heights: list[int]) -> int:
2 ln = len(heights)
3 max_area = 0
4 for left_index in range(ln):
5 left_height = heights[left_index]
6 for right_index in range(left_index + 1, ln):
7 right_height = heights[right_index]
8 width = right_index - left_index
9 height = min(left_height, right_height)
10 area = width * height
11 max_area = max(area, max_area)
12 return max_area
```

- Time complexity:
`O(n²)`

- Space complexity:
`O(1)`

The nested loops produce `O(n²)`

time complexity.

Although the brute force approach does not repeat any calculations, it ignores useful information that can help eliminate unnecessary calculations. For example, if a container has sides `a[i]`

and `a[j]`

such that `a[i] < a[j]`

, all containers with sides `a[i]`

to `a[i+1], ... a[j-1]`

will have a maximum height of `a[i]`

with a smaller width than `j - i`

, producing less area than the original container. Thus, these possibilities do not need to be considered when we're looking for maximum area.

Instead of trying every combination, we start the 2 pointers at opposite ends (indexes `0`

and `n-1`

) to represent the sides of the container. After computing the area using the lower height and distance between the pointers, the options are to increment the left pointer or decrement the right pointer.

Because we want to maximize the water contained, move the pointer with the lower height toward the other pointer. If the heights are equal, we can update either pointer because any potential increase in the next height is limited by one of the equal existing heights. The process is repeated until the pointers meet.

```
_height = heights[right_index]
min_height = min(left_height, right_height)
area = width * min_height
max_area = max(area, max_area)
if left_height <= right_height:
left_index += 1
else:
right_index -= 1
return max_area
```

```
1_height = heights[right_index]
2 min_height = min(left_height, right_height)
3 area = width * min_height
4 max_area = max(area, max_area)
5 if left_height <= right_height:
6 left_index += 1
7 else:
8 right_index -= 1
9 return max_area
```

- Time complexity:
`O(n)`

- Space complexity:
`O(1)`

Because the left or right pointer is moved toward the other in each iteration until they meet, the list of integers is traversed once.

MEDIUM

Data Structures and Algorithms

Build a Max Heap

Given an array of integers, transform the array in-place to a max heap.

HEAPSTREES

Watch 1 interview

MEDIUM

Data Structures and Algorithms

Three Sum

Given an array of integers, return an array of triplets such that i != j != k and nums[i] + nums[j] + nums[k] = 0.

ARRAYSSORTINGHASH MAPSSEARCH

Watch 1 interview

EASY

Data Structures and Algorithms

Reverse Linked List

Given the head of a linked list, reverse the list and return the new head.

LINKED LISTS

Watch 2 interviews

interviewing.io is a **mock interview practice platform**. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.