Container With Most Water
Array, Two Pointers
You are given an integer array height of length n
. 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 that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Example 2:
Assumptions:
There is no number calculation overflow.
There is no any negative value element.
Questions to Clarify:
What would be the size of the input array?
Solutions
As per the problem, we need to find out the maximum area that can hold most water, and the mathematical formula for calculate area is (Length*Width
). In this problem, length is the value of the element, and width is the index gap between two elements.
Here, the area calculation formula for this problem is:
area = min(leftElement,rightElement)*(rightElementIndex-leftElementIndex)
Approach – Brute Force Technique
Run two nested loops to calculate the area between two elements and compare it with the previous area value. If it is greater than the previous one, then set it to the maximum area.
Steps
The algorithm starts by initializing
maxArea
to 0. This variable will keep track of the maximum area found so far.It then checks if the
height
array is not null and has at least 2 elements. If not, it returnsmaxArea
(which is 0) immediately, as you can't form a container with less than 2 lines.The algorithm then enters a nested loop. The outer loop (
i
) goes from 0 to the length of theheight
array. The inner loop (j
) goes fromi + 1
to the length of theheight
array. This way, every pair of lines is considered exactly once.For each pair of lines, it calculates the area of the container they would form. This is done by taking the minimum of the heights of the two lines (since the water would overflow from the shorter line) and multiplying it by the distance between the lines (
j - i
).If the calculated area is greater than
maxArea
, it updatesmaxArea
with the new area.After considering all pairs of lines, it returns
maxArea
, which is the maximum area of water that can be contained.
Complexity
Time complexity:
O(N^2)
Space complexity:
O(1)
Approach – Two Pointers Technique
This problem can be solved using a two-pointer approach. Initialize two pointers, one at the beginning of the array (left
) and one at the end of the array ('right'), calculate the area between them, and move the smaller pointer forward or backward responsively.
Steps
The algorithm starts by initializing
maxArea
to 0. This variable will keep track of the maximum area found so far.It then checks if the
height
array is not null and has at least 2 elements. If not, it returnsmaxArea
(which is 0) immediately, as you can't form a container with less than 2 lines.It initializes two pointers,
left
andright
, to the start and end of the array respectively.It enters a loop that continues until
left
andright
meet. In each iteration of the loop, it does the following:It calculates the area of the container formed by the lines at
left
andright
. This is done by taking the minimum of the heights of the two lines (since the water would overflow from the shorter line) and multiplying it by the distance between the lines (right - left
).If the calculated area is greater than
maxArea
, it updatesmaxArea
with the new area.It then decides which pointer to move. If the height of the line at
left
is less than the height of the line atright
, it moves theleft
pointer one step to the right. Otherwise, it moves theright
pointer one step to the left. The reason for this is that moving the pointer with the smaller height gives us a chance to find a higher line that can potentially lead to a larger area.
After the loop ends, it returns
maxArea
, which is the maximum area of water that can be contained.
Complexity
Time complexity:
O(N)
Space complexity:
O(1)
Last updated