11. Container With Most Water
# O(n) time || O(1) space
def max_area(self, height: List[int]) -> int:
res, low, high = 0, 0, len(height) - 1
while low < high:
res = max(res, (high - low) * (min(height[low], height[high])))
if height[low] <= height[high]:
low += 1
else:
high -= 1
return res
This problem is known as the “Container With Most Water” and is a well-known example of a two-pointer technique.
Here’s the strategy to solve it:
- Initialize two pointers, one at the beginning of the array (
left
) and one at the end (right
). - Calculate the area formed between the lines at the
left
andright
pointers, and update the maximum area found so far. - Move the pointer that points to the shorter line inwards, because if we move the pointer at the taller line, we are sure that the area cannot increase - the width is decreasing, and the height is limited by the shorter line.
- Repeat steps 2 and 3 until the two pointers meet.
The formula to calculate the area between two lines is:
Area = width * height
where width is the difference between the indices of the two lines and height is the minimum of the two line heights.