11. Container With Most Water

Description

See: https://leetcode.com/problems/container-with-most-water/

What I Learned

I did the brute force solution to start with. This solution timed out as I expected it would. But, my math worked out, which showed I understood that part of the problem. I looked at the hint next. I implemented a two pointer solution.

Solution

In this problem we need to find the area between two lines, which forms a rectangle. The largest length between two lines will be the length between the lines at first index and the last index of the array.

The task is then to find if there are other areas that are greater and return the max area. An area may be greater than the initial area, if the height of the line is large enough.

I used a two pointer solution. The left pointer is set to the first index of the array. The right pointer is set to the last index of the array. The area is then calculated based on the formula:

$$area = right - left * min(height[left], height[right])$$

So, on the first iteration, the length (right - left) is the greatest. It is then multiplied by the shortest height, of height[left] and height[right] (heights are stored in the heights array, i.e. height[n]).

However, there could be a greater area, if there is a larger height in the array. So, we need to move the left or right pointer (depending on which is the smaller one). By moving the smaller one, we are attempting to find a larger height, that could cause the area to be greater despite the smaller width.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        left = 0
        right = len(height) - 1
        while left < right:
            area = (right - left) * min(height[left], height[right])
            max_area = max(area, max_area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area