LeetCode #11 – Container With Most Water

Sometimes, coding questions are also part of data science interviews, so here is the solution to LeetCode #11 – the container with the most water problem.

The problem is very straightforward, you’re given a list with n integers, each representing the height of a tower, you’ve to find the maximum area that can be formed with these heights and the x-axis represents the index distance between the integers with a twist that since it represents a block containing water, you’ve to take the min of the two heights as the water has to contained within the towers.

For example, if the list of given heights is h = [1,1,4,5,10,1], the maximum area that can be formed will be 8. It will be between the tower with heights 4 and 10, with an index distance of 2. So the area will be min(4,10)*2 = 8.

Coming to the solution, the easiest solution will be to compare each combination of two tower heights, and return the maximum area that can be formed. This will have a time complexity of

def maxArea(height: List[int]) -> int:
        max_vol = 0
        for i in range(len(height)):
            for j in range(1,len(height)):
                if j<=i:
                    continue
                else:
                    vol = min(height[i], height[j])*(j-i)
                    max_vol = max(max_vol, vol)
        return max_vol

Although the above solution will pass the sample test cases, it will eventually return Time Limit Exceeded as it is a very brute force solution, as it compares almost every possible combination. You can be a bit more clever in your approach and solve this problem in time complexity.

The trick is using pointers, one for left and one for right, starting with the largest width and then storing the max area. Move the left pointer right if you encounter a higher tower in the left otherwise move the right pointer towards the left, and repeat till both pointers meet. In this way, you’ve traversed the list only once.

def maxArea(height: List[int]) -> int:
        l,r = 0,len(height) - 1
        max_vol = -1
        while l < r:
            #Calculating the shorter height of the two
            shorter_height = min(height[l], height[r])
            width = r-l
            vol = shorter_height * width
            max_vol = max(vol, max_vol)
            if height[l] < height[r]:
                l+=1
            else:
                r-=1
        return max_vol

Taking an example, if input is [1,4,5,7,4,1], then.