Interview challenge · medium · array, two-pointers, greedy
Container With Most Water
The challenge
Given an array height where each value is the height of a vertical line, pick two lines that, together with the x-axis, form a container holding the most water. The water held is the distance between the lines times the shorter of the two. Return that maximum area.
Example
[1, 8, 6, 2, 5, 4, 8, 3, 7] -> 49 (lines 8 and 7, 7 apart)
[1, 1] -> 1
[4, 3, 2, 1, 4] -> 16Idea: two pointers, one at each end. The area is limited by the shorter wall, so moving the taller one inward can never help: move the shorter one and keep the best area seen. Time O(n), space O(1).
The solution
# Container With Most Water - ayotl.dev
def max_area(h):
# two pointers, one at each end
i, j, best = 0, len(h) - 1, 0
while i < j:
area = (j - i) * min(h[i], h[j])
best = max(best, area)
# move the shorter wall inward
if h[i] < h[j]:
i += 1
else:
j -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))
print(max_area([1, 1]))
print(max_area([4, 3, 2, 1, 4]))
$ python3 container_with_most_water.py
49
1
16