# Container With Most Water

##### January 8, 2024

## Problem #

Given n non-negative integers `a1, a2, ..., an`

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

. `n`

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

is at `(i, ai)`

and `(i, 0)`

. Find two lines, which, together with the x-axis, forms a container, such that the container contains the most water. You may not slant the container.

**Example**:

- Input: [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The max area of water the container can contain is 49.

### Solution #

The solution uses a two-pointer approach. Start with one pointer at the beginning and one at the end of the array. Calculate the area between the two pointers and update the maximum area found so far. Then, move the pointer pointing to the shorter line towards the other pointer. This is because moving the longer line will not increase the area. The process is repeated until the two pointers meet.

### Algorithm Steps #

- Initialize two pointers,
`left`

at the start and`right`

at the end of the array. - Initialize a variable
`maxArea`

to store the maximum area found. - While
`left`

is less than`right`

:- Calculate the area with
`min(height[left], height[right]) * (right - left)`

and update`maxArea`

. - Move the pointer with the shorter height inwards.

- Calculate the area with
- Return
`maxArea`

.

#### Code (Python) #

```
def maxArea(height):
left, right = 0, len(height) - 1
maxArea = 0
while left < right:
width = right - left
currentArea = min(height[left], height[right]) * width
maxArea = max(maxArea, currentArea)
if height[left] < height[right]:
left += 1
else:
right -= 1
return maxArea
# Test the function
print(maxArea([1,8,6,2,5,4,8,3,7])) # Output: 49
```

#### Time Complexity #

The time complexity is O(n), where n is the number of elements in the array. This is due to the single pass through the array.

#### Space Complexity #

The space complexity is O(1), as no extra space is needed apart from variables for iteration and calculation.