Maximum Equal Sum of Three Stacks

Maximum Equal Sum of Three Stacks is a classic greedy problem. You have three stacks of different heights, and you want to make their sums equal by removing items only from the tops. The trick is realizing you never have a real choice about which stack to shrink.

The slow way first

You might try every combination of how many elements to pop from each stack — pop i from A, j from B, k from C, and check every triple for a match. With three stacks of height n that is O(n³) combinations, and it explores choices that can never help.

The question to ask: if the three sums are unequal, is there ever a reason to shrink the smallest one? No. Shrinking the smallest stack only pushes it further below the others — it can never bring them together. So at every moment there is exactly one sensible move.

The idea: always pop the tallest sum

Compute the three sums. While they are not all equal, pop the top of whichever stack has the largest sum. That is the only move that can reduce the gap. Repeat until all three sums match. Because each pop strictly lowers the biggest sum, the sums march toward each other and the process always terminates.

The key insight: greedily reducing the largest sum is safe. We never overshoot a better answer, because any equal height we could reach must be reachable by lowering whichever stack is currently tallest.

Walk through it

Step through the animation. Sums start at A = 8, B = 9, C = 7. B is tallest, so we pop its 4 (B drops to 5). Now A = 8 is tallest, pop its 3 (A drops to 5). Now C = 7 is tallest, pop its 1 (C drops to 6), still tallest, pop another 1 (C drops to 5). All three equal 5 — done.

Pseudocode

a = sum(stack A); b = sum(stack B); c = sum(stack C)
while not (a == b == c):
    m = the largest of a, b, c
    if a is m:  a = a - pop top of A
    else if b is m:  b = b - pop top of B
    else:  c = c - pop top of C
return a            # all three are now equal, so any of them works

The Python solution

def max_equal_sum(s1, s2, s3):
    a = sum(s1)
    b = sum(s2)
    c = sum(s3)
    while not (a == b == c):
        m = max(a, b, c)
        if a == m: a -= s1.pop(0)
        elif b == m: b -= s2.pop(0)
        else: c -= s3.pop(0)
    return a

• We keep s1, s2, s3 as lists with the top of the stack at index 0, so pop(0) removes a top.
• a, b, c hold the running sums so we never re-add a whole stack each round.
• Line 5 is the loop guard: keep going while the three sums are not all equal.
• m = max(a, b, c) finds the largest sum; lines 7-8 pop exactly that stack and subtract the removed value.
• When the loop exits all three are equal, so return a returns the maximum equal sum.

Complexity

Every pop permanently removes an element, so across the whole run we pop at most n times total. That makes it a single linear pass over the data, using only the three running sums for extra space.

When this pattern shows up

Practice