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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Container With Most Water

Number: 11

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg, Microsoft, Meta, Goldman Sachs, Oracle, SAP, TikTok, Apple, ServiceNow, Visa, Accenture, Snowflake, Zopsmart, Mastercard, Adobe, Yahoo, Flipkart, Uber, Tesla, Zoho, eBay, Yandex, Citadel, Bosch, Lenskart, Wix

Problem Description

Given an array height where each element represents the height of a vertical line on the x-axis, find two lines that, along with the x-axis, form a container holding the maximum amount of water.

Key Insights

  • The container's area is determined by the distance between two lines multiplied by the shorter line's height.
  • A brute-force approach checking all possible pairs would result in O(n^2) time complexity, which is inefficient for large inputs.
  • A two-pointer approach allows us to solve the problem in O(n) time by initializing pointers at both ends and gradually moving them inward.
  • By always moving the pointer corresponding to the shorter line, we are more likely to find a taller line that could potentially form a container with a larger capacity.

Space and Time Complexity

Time Complexity: O(n) - The algorithm makes a single pass through the array with two pointers. Space Complexity: O(1) - Only a few extra variables are used, regardless of the input size.

Solution

The optimal approach uses a two-pointer strategy:

  1. Start with two pointers at each end of the array.
  2. Calculate the area formed between the two lines at these pointers.
  3. Update the maximum area if the calculated value is larger.
  4. Move the pointer pointing to the shorter line inward, as this is the only possible way to potentially increase the height of the shorter line and thus the area.
  5. Continue until the two pointers meet.

This method effectively reduces the number of comparisons and ensures that every possible pair that can yield a larger area is considered.

Code Solutions

# Function to calculate the maximum water container area
def maxArea(height):
    left, right = 0, len(height) - 1  # Initialize two pointers
    max_water = 0  # Variable to store the maximum area
    
    # Loop until pointers meet
    while left < right:
        # Calculate current area based on smaller height and distance between pointers
        current_area = min(height[left], height[right]) * (right - left)
        max_water = max(max_water, current_area)  # Update maximum area if current is larger
        
        # Move the pointer corresponding to the smaller height
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

# Test the function with an example
if __name__ == "__main__":
    input_heights = [1,8,6,2,5,4,8,3,7]
    print(maxArea(input_heights))  # Expected output: 49
← Back to All Questions