You’re given an integer array height of length $n$, and there are $n$ vertical lines drawn such that the two endpoints of the $i^{th}$ line are $(i, 0)$ and ($i$, height[i]).

Find two lines from the input array that, together with the x-axis, form a container that holds as much water as possible. Return the maximum amount of water a container can store.

Note: You may not slant the container.

Constraints:

• $n =$ height.length

• $2 \leq$ $n$ $\leq 10^3$

• $0 \leq$ height[i] $\leq 10^3$

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

A naive approach to solve this problem would be to find the area of every possible pair of vertical lines and select the maximum area out of them.

The time complexity for this approach would be $O(n^2)$, where $n$ is the length of the input array. The space complexity would be $O(1)$, since only a constant amount of extra space is used.

An optimized approach to solve this problem is using two pointers, start and end, initialized at the beginning and end of the array, respectively. We also create a variable to store the maximum area and set it to zero.

While iterating through the array, height, the algorithm proceeds through the following steps:

• Calculate the distance, width, between the two vertical lines pointed by start and end pointer as width $=$ end $-$ start.
• The height of the container is determined by the shorter of the two vertical lines pointed by the start and end pointers. Then, multiply this height by the width to calculate the area of the container.
• If the calculated area is greater than the current value of the maximum area, update the maximum area.
• Move the pointer pointing to the shorter vertical line inward by one step. This is because if we try to move the pointer at the longer vertical line, we won’t gain any increase in area, since the shorter line limits it.
• Keep iterating through the array until the pointers meet.

After iterating through the array, return the maximum area.

Now, let’s look at the following illustration to get a better understanding of the solution: