LeetCode 11 - Container With Most Water - 2023.10.10 solution

class Solution:
    def maxArea(self, height: List[int]) -> int:
        """ Thought process: We want a smart way to test the different possible
        combinations.  If we start with two pointers at the two ends of the
        container, the question we should ask ourselves is: "What rule should we
        follow to test new options intelligently?"  In this case, the leftmost
        line is very short, while the rightmost line is very tall.  So the volume
        is limited by the height of the shorter line.  Moving in the right pointer
        will *never* be able to result in a larger volume than that initial volume
        because the limitation was the *left* line.  So we should instead move in
        the left pointer and see if we can get it to be a taller line.  So the
        general rule seems to be: keep track of the indices and the volume of the
        largest combination you've found so far, and then step inwards with the
        pointer of the shorter line to see if you can find a taller line that would
        make up for the loss of width with greater height.  When the two pointers
        are pointing at the same line, stop and return whatever the best combination
        was. [Update: We don't need the indices, just the volume.]

        I had a bug where my step conditional was comparing l and r instead of the
        *heights* at l and r.
        """
        best_volume = 0

        l = 0
        r = len(height) - 1

        while l < r:
            current_container_height = min(height[l], height[r])
            current_volume = (r - l) * current_container_height

            if current_volume > best_volume:
                best_volume = current_volume

            if height[l] > height[r]:
                r -= 1
            else:
                l += 1
        return best_volume