11. Container With Most Water

The problem requires us to find the maximum area between vertical lines of different heights at different separations.

Approach 1: Brute Force

As always, brute forcing is the first solution that strikes. For each of the lines look at all the other lines to see if they enclose an area greater than what we have already seen. Although not expected to pass, I still went ahead and tried this solution just in case the test cases weren't extremely large.

def maxArea(self, height):     
    """     
    :type height: List[int]     
    :rtype: int     
    """     
    lh = len(height)     
    max_vol = -1     
    for i in range(lh):         
        for j in range(i+1, lh):             
            if i == j:                 
                continue             
            if (j-i)*min(height[i],height[j]) > max_vol:                 
                max_vol = (j-i)*min(height[i],height[j])     
    return max_vol

As expected, the test cases were large enough that the time limit exceeded on test case 41/49

Time Complexity: O(n²)

Space Complexity: O(1)

Approach 2: Two Ends Approach

This one took some serious help to come up with. Drawing diagrams on a whiteboard didn't seem to help since I could not get rid of the second loop

The fix to that problem was to start at the ends of the array and then each time move the end with the shorter height to the next one.

This approach ensured that the array was only looked at once and reduced the runtime by a factor of n

def maxArea(self, height):
    """
    https://leetcode.com/problems/container-with-most-water/description/
    :type height: List[int]
    :rtype: int
    """
    max_area = area = 0
    left, right = 0, len(height) - 1
    while left < right:
        l, r = height[left], height[right]
        if l < r:
            area = (right - left) * l
            while height[left] <= l:
                left += 1
        else:
            area = (right - left) * r
            while height[right] <= r and right:
                right -= 1
        if area > max_area:
            max_area = area
    return max_area

As expected this solution was accepted.

Time Complexity: O(n) (Only one pass)

Space Complexity: O(1)