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.
time-limit-exceeded
tag to your question. \$\endgroup\$