Blind 75.09 - Container with Most Water

Container with most water.

Problem description

Taken directly from LeetCode.

(use html to markdown converter: https://codebeautify.org/html-to-markdown)

Solution type

how rectangles work lol

Solution

I can never remember how this one works…

The brute force \(O(n^2)\) solution is to just check all pairs, see how much water you store, and track the maximum volume of water you can store. What I can’t remember is what characteristic you use from the problem to reduce that work to \(O(n)\).

Well, let’s start by considering the volume stored by lines at indices 0 and n-1. We’ll refer to them as left and right indices for now. This maximizes the width of our container; we will not choose different indices unless those different indices result in a greater height, because choosing different indices would reduce the width and in turn reduce the total volume of water we can store. The height of our container is the minimum of height[left], height[right].

Now how do we choose which index to change? Well, we want to increase our minimum, so we should increment¹ whichever of left or right has a smaller value. In the case of [1,8,6,2,5,4,8,3,7], if we initialize left = 0and right = 8, then we will increment left to index 1 to get a new minimum of 7 between height[left], height[right]. We stop searching once left == right. Even though our array isn’t sorted (which might make it seem like this shouldn’t work), this approach of greedily increasing the maximum works because we only ever consider indices that would increase the height (since width is always decreasing), and the only way we can get a higher volume than spanning the entire container is if we increase the height (again, because width is always decreasing).

Here’s a tricky edge case: what about ties? In other words, where left and right are equal to the same value? ~~In this case, we should increment left and decrement right until we get new values for them, then set a ~~ I’m not actually sure anymore if this is a problem. Height again is determined by the minimum, so if the two heights are the same value then both values need to change in order to get a possibly higher water volume. If you never consider other values for one of the indices, that’s not an error - that means you never had a chance to have a higher area in the first place.

Wow. Much easier than I thought it would be.

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

I just remember this being so hard back in the day…I guess not anymore? I think the fundamental realization you have to make is that you want an algorithm where width decreases over time. Once you make that realization, you just need to think about how the rectangle area calculation works and you’re good.

Well, feeling good about that one! :D

1. I should say that we decrement right. I’m just being lazy right now. ↩