How to speed up the code for LeetCode "Container with most water" task? 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) -&gt; 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] &gt;= 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)
My suggestion about your current solution:
def max_area(height) -&gt; 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] &gt;= 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) -&gt; 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] &gt;= 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 &lt;= 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 &quot;hints&quot; and the tab &quot;Discuss&quot; for help or alternative solutions.