We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Container With Most Water

Difficulty: Medium

Problem Description

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.

Key Insights

  • The area of water contained by two lines is determined by the shorter line and the distance between the two lines.
  • To maximize the area, we should consider the lines that are farthest apart while having the tallest heights.
  • A two-pointer technique can efficiently find the solution by starting with the widest container and moving inward based on the heights.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The problem can be solved using a two-pointer approach. We initialize two pointers, one at the beginning and one at the end of the height array. The area is calculated by taking the minimum height of the two lines multiplied by the distance between the pointers. We then move the pointer pointing to the shorter line inward, hoping to find a taller line that could potentially increase the area. This continues until the two pointers meet.

Code Solutions

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        width = right - left
        current_height = min(height[left], height[right])
        max_area = max(max_area, current_height * width)
        
        # Move the pointer for the shorter line
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
            
    return max_area
← Back to All Questions