Container With Most Water Leetcode Solution
In this tutorial, we are going to solve a leetcode problem, Container with most water in python.
Task:
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith 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:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
Solution:
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
area = 0
while left < right:
m = min(height[left], height[right])
cal = (right - left) * m
if cal > area:
area = cal
a1 = min(height[left+1], height[right])
a2 = min(height[left], height[right-1])
if a1 > m:
left += 1
elif a2 > m:
right -= 1
elif height[left] < height[right]:
left += 1
elif height[left] >= height[right]:
right -= 1
return area
Steps:
step1: First, we are going to approach this problem with two pointers traditional approach.
step2: we initiate 2 pointers left and right pointing to 0 and last index of height and variable area = 0.
step3: Now, we run a while loop for left < right and inside the loop we declare a variable m which is equal to the minimum of value at index left+1 and right and cal variable stores the required area which is basically length * breadth.
step4: Now, if the cal is greater than area than we area is equal to cal, which is our current calculated area.
step5; Now after that we declare two more variables a1 & a2 which is equal to minimum of value at index left+1 and right & for a2 the index would be left and right-1.
step6: Now, that we have a1 and a2 we can compare it to m which is initially our minimum value and we update the pointers basedon these a1 & a2 variable if one of these is greater than m, otherwise we update left and right based on their current values. And after the loop we return area as required answer.
