Solving Container With Most Water

Start one pointer at each end of the array and move whichever points at the shorter wall inwards. At every step, compute the area as the shorter wall times the width between the pointers and keep the best.

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        if area > best:
            best = area
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))
print(max_area([1, 1]))

The outputs are 49 and 1. For the first array the best container uses the wall of height eight at index one and the wall of height seven at index eight, giving seven times eight, which is 49. The second array can only hold one unit of water because both walls are one high.

The greedy argument is the heart of the solution. Suppose the left wall is shorter than the right wall. Any container that uses the left wall and a different right wall is narrower, so its area is at most the left height times a smaller width, which is strictly less than what the current pair already achieves. Therefore the left wall can never be part of a better answer, and discarding it is safe. The mirror argument applies when the right wall is shorter.

The trade-off to state is that this beats the brute force scan, which tries every pair of walls and costs O of n squared, by exploiting the monotonic relationship between width and height. The two pointers version is O of n time and O of 1 space. The only caveat is that it is a one-pass greedy argument: it relies on the area being the product of the shorter wall and the width, and that relation is what makes discarding the shorter wall safe.

The algorithm does not change at all; you simply record the pair of indices whenever you find a larger area. Keeping the best pair alongside the best value costs one extra assignment and nothing in complexity terms.

def max_area_pair(height):
    left, right = 0, len(height) - 1
    best = 0
    best_pair = (0, 0)
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        if area > best:
            best = area
            best_pair = (left, right)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best, best_pair

print(max_area_pair([1, 8, 6, 2, 5, 4, 8, 3, 7]))

The output is 49 and the pair one and eight. The walls at those positions have heights eight and seven, and there are seven columns between them, so the area is seven times seven, which is 49.

Walking the loop makes it obvious why that pair wins. The first pair, indices zero and eight, has walls of height one and seven, so the area is one times eight, which is eight. The left pointer then moves inwards because one is the shorter wall. The next pair, indices one and eight, has walls of height eight and seven across seven columns, giving 49, and no later pair can beat it. From there the right pointer walks inwards and every area it measures is smaller: 18, 20, 16, 15, 4, and then 6 for the last pair.

The trade-off to name is that returning indices rather than a value is often what the caller actually needs, because the indices let the caller identify the objects involved, for example to mark them in a report. The cost is a couple of extra variables and a slightly larger return type. The complexity stays O of n time and O of 1 space, and the greedy argument is untouched, since recording a better answer does not change which pointer moves.

The brute force approach tries every pair of walls. You loop over the first wall, loop over every later wall, compute the area as the shorter wall times the distance between them, and keep the maximum. That is a double loop over n elements, so it costs O of n squared time and O of 1 space.

The two pointers version replaces the inner loop with a single sweep from both ends, which brings the cost down to O of n time. The saving comes from the greedy observation: at any point, one of the two walls currently pointed at can be discarded outright, because any pair that includes that wall and a narrower partner cannot beat the pair you are already holding. So each iteration eliminates one candidate permanently, and the whole scan performs n steps instead of n squared pairs.

The saving is not a constant factor; it is a change of class. On an array of ten thousand walls the brute force version evaluates about fifty million pairs while the two pointers version evaluates fewer than ten thousand. That is the difference between a solution that times out and one that returns instantly, and it is the reason interviewers care about the greedy proof rather than just the code.

The trade-off to mention is the precondition. The greedy step is only sound because the area of a container is the shorter wall times the width. If the problem were modified so that the area depended on something else, such as the sum of the walls, the same reasoning would not apply and you would be back to the quadratic scan or a different structure entirely.