Maximum Score From Removing Stones: Greedy Math

You are given three piles of stones with sizes a, b, and c. Each turn, you pick two different non-empty piles, remove one stone from each, and score one point. The game ends when you can no longer pick two non-empty piles. Return the maximum score you can achieve.

This is LeetCode 1753: Maximum Score From Removing Stones, a medium problem that teaches the pile balancing pattern. The key is recognizing that you do not need to simulate each turn. A simple math formula gives you the answer in constant time.

Why this problem matters

This problem looks like it requires simulation or dynamic programming, but it has an elegant closed-form solution. It teaches you to step back and think about the structure of a problem before jumping into code. The insight here is about balance: when one pile is large enough to absorb everything from the other two, those smaller piles become the bottleneck. When all three piles are balanced, you can drain them almost completely.

This kind of greedy math reasoning shows up in resource allocation, scheduling, and pairing problems. Learning to recognize when a problem has a formula instead of a loop is a valuable skill.

The key insight

Sort the three values so that a is the smallest and c is the largest. Now consider two cases:

1. The largest pile dominates. If c >= a + b, then you can pair every stone in piles a and b with a stone from pile c. Once a and b are empty, you have leftover stones in c that you cannot use (you need two non-empty piles). The answer is a + b.

2. The piles are balanced. If c < a + b, the three piles are close enough in size that you can keep pairing stones across all three piles until at most one stone remains. The answer is (a + b + c) // 2. The floor division accounts for the case where the total is odd and one stone is left unpaired.

The algorithm is:

1. Sort a, b, c so that a is the smallest and c is the largest.
2. If c >= a + b, return a + b.
3. Otherwise, return (a + b + c) // 2.

The solution

def maximumScore(a, b, c):
    a, b, c = sorted([a, b, c])
    if c >= a + b:
        return a + b
    return (a + b + c) // 2

That is the entire solution. Three lines of logic after sorting. The sorted call ensures a is the smallest and c is the largest. Then the single branch covers both cases.

Why does the balanced case work? Think of it this way: each turn removes exactly two stones from the total. You start with a + b + c stones. Each turn reduces the total by 2 and scores 1 point. The game ends when at most one pile is non-empty (you need two non-empty piles to continue). If the piles are balanced, you can always pick the two largest piles and reduce them, eventually leaving at most one stone. So the number of turns is floor(total / 2).

Visual walkthrough

Let's trace through the formula on several examples to build intuition for both cases.

Notice how the formula handles both extremes cleanly. When one pile is huge, a + b caps the score. When piles are balanced, floor(total / 2) gives the exact number of pairing rounds.

Complexity analysis

Time: Sorting three elements is constant work. The comparison and arithmetic are O(1). No loops, no recursion. Space: Only a few variables are used. No extra data structures needed.

The building blocks

1. Greedy pile pairing

The pattern of always picking two non-empty piles to maximize turns is a greedy choice. In the balanced case, the optimal strategy is to pick the two largest piles each turn. This keeps the piles as balanced as possible, which maximizes the number of rounds before one pile is isolated.

piles = sorted([a, b, c])
if piles[2] >= piles[0] + piles[1]:
    return piles[0] + piles[1]
return sum(piles) // 2

This greedy reasoning applies to many pairing and matching problems: pair the extremes, keep things balanced, and check whether one element dominates.

2. Floor division for total pairing

When a total quantity is consumed two units at a time, the maximum number of rounds is total // 2. This pattern appears whenever you are pairing elements and want to know the maximum number of pairs.

total = a + b + c
max_pairs = total // 2

This building block shows up in problems about matching socks, pairing students, or distributing items evenly. The floor division captures the fact that an odd leftover cannot form a pair.

Edge cases

• One pile is zero (0, 5, 3): after sorting, a=0, b=3, c=5. Since c >= a + b (5 >= 3), answer is a + b = 3. You pair b with c.
• Two piles are zero (0, 0, 7): after sorting, a=0, b=0, c=7. Since c >= a + b (7 >= 0), answer is 0. You cannot pick two non-empty piles.
• All piles equal (5, 5, 5): total = 15, c < a + b (5 < 10), answer is 15 // 2 = 7.
• All piles are one (1, 1, 1): total = 3, c < a + b (1 < 2), answer is 3 // 2 = 1.
• Large pile exactly equals sum (3, 4, 7): c = 7 >= 3 + 4 = 7, answer is 3 + 4 = 7. The boundary is inclusive.
• Very large values (10000, 10000, 10000): total = 30000, answer is 15000. The formula handles large inputs without simulation.

From understanding to recall

The formula for this problem is short, but the reasoning behind it is what matters. In an interview, you need to explain why c >= a + b is the threshold and why floor(total / 2) works in the balanced case. If you just memorize the formula without understanding the two cases, you will struggle to adapt when the problem changes slightly.

Spaced repetition helps you internalize both the formula and the reasoning. You practice deriving the two cases from scratch, explaining the greedy argument, and writing the three-line solution from memory. After a few rounds, the pile balancing pattern becomes automatic. You see "pair elements from groups to maximize rounds" and the analysis flows naturally.

The greedy pile pairing pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Lemonade Change - Another greedy problem about making optimal choices
• Jump Game - Greedy decision-making with constraints
• Gas Station - Greedy circular problem solving

CodeBricks breaks the maximum score from removing stones problem into its greedy pile pairing and floor division building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy pairing question shows up in your interview, you do not think about it. You just write it.