DEV Community 👩‍💻👨‍💻

Bernice Waweru
Bernice Waweru

Posted on

Container With Most Water

Instructions

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

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The max area of water in the container can contain is 49.
Enter fullscreen mode Exit fullscreen mode

Approach

Basically, this problem involves getting the area of a rectangle by multiplying the length and width.
We can initialize a left and right pointer where the left starts at the height[0] and the right starts at height[-1] to maximize the width.
We can then compare the right and left pointers and shift the one with the lowest value to attempt to increase the area by changing the height. We then update the maximum area as we shift the pointers.

Python Implementation

def maxArea(height):
        left = 0
        right = len(height) -1
        max_area = 0   
        while left < right:
            areas = (right-left) * min(height[left],height[right])
            max_area = max(max_area,areas)
            if height[left] < height[right]:
                left +=1
            elif height[left] > height[right]:
                right -=1
            else:
                right-=1
        return max_area
Enter fullscreen mode Exit fullscreen mode

We can also implement the two-pointer approach as follows:

def maxArea(height):
    # start looking from both ends of the array
    l, r = 0, len(height) - 1
    max_area = 0
    while l < r:
        if height[l] < height[r]:
            area = height[l] * (r - l)
    # height at the left is smaller so we should look for the larger heights by moving towards right.
            l += 1
        else:
            area = height[r] * (r - l)
    # height at the right end is smaller so we move towards the left.
            r -= 1
        if area > max_area:
            max_area = area
    return max_area
Enter fullscreen mode Exit fullscreen mode

I hope you found this helpful

Top comments (0)

🌚 Friends don't let friends browse without dark mode.

Good news! You can update to dark mode in your DEV settings.