## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Container with most water challenge

Sharing is caring!

Problem statement

Given n non-negative integers $a_1, a_2, \dots, a_n$, where each represents a point at coordinate $(i, a_i)$. $n$ vertical lines are drawn such that the two endpoints of line $i$ is at $(i, a_i)$ and $(i, 0)$. Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and $n$ is at least $2$.

Solution
We are going to solve this problem using two pointers `l` and `r`. Pointer `l` starts from the left-most side and `r` starts from the right-most side. We then keep track of our `maximum` container:

```maximum = max(maximum, min(height[l], height[r]) * (r - l))
```

and then move one of the pointers based on the following conditions:

```if height[l] < height[r]:
l += 1
else:
r -= 1
```

Let us explain the logic behind this algorithm using the illustration below.

For wall $A$ we want to use wall $D$ as its counterpart since $D$ is taller than $A$ and as far on the right as possible. Any wall to the left of $D$ can be ignored because it will only make our container smaller as $D$ is already taller than $A$. That is why it doesn't make any sense to decrease our index `r`. With $A$ and $D$ we have a container size of $3$.

We then increment our index 'l' because $A$ is shorter than $D$. That is, move it to wall $B$ in hopes that we can find a taller counterpart for our tall wall $D$. Now, wall $B$ is taller than its predecessor and actually increases our container size to $4$. We can see that since we previously increased the index pointing to the shorter of the two walls ($A$ vs $D$) we were able to find a counterpart ($B$) for wall $D$ that increased our container size.

Finally we again increase our index pointing to the shortest wall in hopes that we may find an even taller counterpart for $D$. Moving `l` to $C$ we see that this does not increase our container size. Also since `l` and `r` meet, we stop the search and return $4$.

The full code is listed below.

Full code

```class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
l = 0
r = len(height) - 1
maximum = 0
while l < r:
maximum = max(maximum, min(height[l], height[r]) * (r - l))
if height[l] < height[r]:
l += 1
else:
r -= 1

return maximum```