Description
Choose two vertical lines whose heights and horizontal distance enclose the largest area. There are at least two nonnegative heights.
Solution
def max_area(height):
left, right, best = 0, len(height)-1, 0
while left < right:
best = max(best, (right-left)*min(height[left], height[right]))
if height[left] < height[right]:
left += 1
else:
right -= 1
return bestExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[2,6,4,5]]- Output
10
Heights 6 and 5, two positions apart, enclose area 10.
Example 2
- Input
[[1,1]]- Output
1
Unit height times unit distance gives one.
Example 3
- Input
[[0,0]]- Output
0
Zero heights cannot enclose water.
Approach
Start at the ends and discard the shorter boundary after evaluating its area.
Time & space
O(n) time; O(1) space. Here n is the input length.