Solving in python — LeetCode #11

Read the problem description here : https://leetcode.com/problems/container-with-most-water/

Given a list of integers, where each value of the list represents height of a line at that index, the goal is to find the area of the largest rectangle the given lines can enclose. This would technically be the area contained within the tallest lines that are placed furthest apart.

To start off, let’s write a utility function that can find the area of any rectangle given indices of two lines and the height of lines at those indices. (Technically, if the list was global, just the indices would be enough)

def findArea(self, XOne, YOne, XTwo, YTwo) -> int:
        width = abs(XOne-XTwo)
        height = YOne if YOne<YTwo else YTwo
        return width*height

The above function considers the lowest height because the enclosure would break if the higher line was considered to be the height (in accordance to the question).

Now that that’s out of the way — the first obvious solution is brute force. Iteratively, go through each index, & find area with the line at every other other index. This would be an O(n)² solution, and would potentially break the time limitation on at least one of the test cases.

def maxArea(self, height: List[int]) -> int:
        maxArea = -1
        for i in range(len(height)):
            for j in range(len(height)):
                if i==j :
                    continue
                currentArea = self.findArea(i,height[i],j,height[j])
                if maxArea<currentArea :
                    maxArea = currentArea
        return maxArea

A relatively greedy approach can be to find the tallest lines first & take the area enclosed by them. But, we do have to realise that two small lines place far enough apart can yield a higher area than two tall lines place close together. 1x50 > 7x7.

We have the max length of the array i.e. the max width of any rectangle, and can possibly use that to determine what is the minimum height of rectangle we need to obtain the said area. I thought a lot about how to utilise the above two lines of thought into a solution but couldn’t find any. Maybe someone else has thought of a way and, I’d be really happy to discuss this further.

The best solution I could think of was using a two pointer approach, we start with

left=0, right=len(array)

increment left when array[left]<array[right], and decrement right otherwise. Keep a track of maximum area found and replace it if currentArea is higher.

def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height)-1
        maxArea = -1
        while left<right :
        
            currentArea = self.findArea(left, height[left], right, height[right])
            maxArea = currentArea if currentArea>maxArea else maxArea
            
            if(height[left]<height[right]) :
                left = left+1
            else:
                right = right-1
        return maxArea

I’m trying to not look at any solutions, so, that was my best effort. If somebody has a better solution and would like to add it in comment, I’ll be really happy to discuss.