How to speed up the code for LeetCode "Container with most water" task?

Question

I'm trying to solve the LeetCode question where you need to find out the area of the container with the most water. I have created the solution that seems to work in my testing but it fails for being too slow when I try to submit it on LeetCode.

My idea is that I create a dictionary of (x, y) tuples from the input list and then for every item I need to find the maximum distance to any of other lines that are equal or taller than it and from here I can calculate what the maximum area is possible for this line.

How else can I approach this to get it to run faster? (I can't submit solution successfully so can't see examples of answers by other users)

def max_area(height) -> int:
    areas = []
    coords = {x: (x, y) for x, y in enumerate(height)}
    for x in coords:
        higher = [k for k in coords if coords[k][1] >= coords[x][1]]
        area = max(abs(coords[j][0] - coords[x][0]) for j in higher) * coords[x][1]
        areas.append(area)
    return max(areas)

Answer 1

Your question made me want to give it a shot, too. The solution ended up pretty much like the pseudo-code suggested by @Marc , and Python is of course pretty close in readability anyway. The below code passes on the site and runs (there is some deviation between runs) faster than c. 95% and at with less memory usage than c. 75% of solutions. The code contains comments at the relevant positions. There's two extra optimizations, also explained there.

def max_area(height: list[int]) -> int:
        n = len(height) - 1
        l = 0  # Index for left bar
        r = n  # Index for right bar
        max_area = 0

        while True:
            # Give readable names:
            left = height[l]
            right = height[r]

            # Current area, constrained by lower bar:
            area = min(left, right) * (r - l)
            if area > max_area:
                # Keep tabs on maximum, the task doesn't ask for any
                # more details than that.
                max_area = area

            # Move the smaller bar further inwards towards the center, expressed
            # as moving left, where *not* moving left implies moving right.
            # The smaller bar constrains the area, and we hope to get to a longer
            # one by moving inwards, at which point the other bar forms the constraint,
            # so the entire thing reverses.
            move_left = left < right

            # Instead of only moving the smaller bar inward by one step, there's two
            # extra steps here:
            #    1. While moving the smaller bar inward, skip all bars that are
            #       *even smaller*; those are definitely not the target, since both
            #       their height and horizontal delta will be smaller.
            #    2. While skipping all smaller bars, we might hit the other bar:
            #       there is a 'valley' or at least nothing higher in between.
            #       Any more moving inwards would be a wasted effort, no matter the
            #       the direction (from left or right). We can return the current
            #       max. area.
            #
            # In the best case scenario, this may skip us right to the solution,
            # e.g. for `[10, 1, 1, 1, 1, 1, 10]`: only one outer loop is necessary.
            #
            # Both loops look very similar, maybe there's room for some indirection
            # here, although a function call would probably mess with the raw
            # performance.
            if move_left:
                while height[l] <= left:
                    if l == r:
                        return max_area
                    l += 1
            else:
                while height[r] <= right:
                    if r == l:
                        return max_area
                    r -= 1


# Examples from the site
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49)
print(max_area([2, 3, 10, 5, 7, 8, 9]) == 36)
print(max_area([1, 3, 2, 5, 25, 24, 5]) == 24)

---

As far as your code goes:

• The mapping

  coords = {x: (x, y) for x, y in enumerate(height)}
  

  seems pretty odd. You're kind of mapping x to itself. I would say for the solution it's much simpler to not treat x as x in the "2D math plot" sense, but just as i in the array index sense. This saves us having to even declare x, we can just iterate using i.

• You use max twice, which is a linear search operation each time. This is needlessly expensive, but probably not the bottleneck.

• Any algorithm based on finding e.g. all distances to every other item for every item has explosive complexity. This is likely the bottleneck.

Answer 2

My suggestion about your current solution:

def max_area(height) -> int:
    areas = []
    coords = {x: (x, y) for x, y in enumerate(height)}
    for x in coords:
        higher = [k for k in coords if coords[k][1] >= coords[x][1]]
        area = max(abs(coords[j][0] - coords[x][0]) for j in higher) * coords[x][1]
        areas.append(area)
    return max(areas)

• Keep track of the biggest area so far, instead of using the list areas.

def max_area(height) -> int:
    coords = {x: (x, y) for x, y in enumerate(height)}
    result = 0
    for x in coords:
        higher = [k for k in coords if coords[k][1] >= coords[x][1]]
        area = max(abs(coords[j][0] - coords[x][0]) for j in higher) * coords[x][1]
        result = max(result, area)
    return result

This reduces memory usage but is not enough to pass the challenge.

The solution can be considered a brute force approach which is typically not enough to solve medium/hard problems on LeetCode.

The constraint is \$n <= 3 * 10^4\$, where \$n\$ is the length of the input list. Generally, with such constraint, we should look at a solution with a time complexity less than \$O(n^2)\$.

Let's consider the example on LeetCode where the input list is:

• height = [1,8,6,2,5,4,8,3,7]

For each two bars, the biggest area is given by the lowest bar. In the example, the two bars are 8 and 7, so the area is 7 * (8 - 1) = 49. Note that (8 - 1) is the difference between the indices of the bars. This is an \$O(n)\$ algorithm:

Initialize l to 0
Initialize r to the right most index
Initialize max_area to 0
while l is lower than r
    find the area as: lowest bar * (r - l)
    update max_area
    increment l if points to the lower bar, else decrement r
return max_area

Next time you can check the "hints" and the tab "Discuss" for help or alternative solutions.