Maximum Number of Coins You Can Get: Greedy Triplet Picking

There are 3n piles of coins of varying sizes. In each round, you pick any three piles. Alice always takes the pile with the most coins, you take the pile with the second most, and Bob takes the pile with the fewest. After all piles are gone, return the maximum number of coins you can collect.

This is LeetCode 1561: Maximum Number of Coins You Can Get, a medium problem that rewards a clean sorting-based greedy strategy. The key question is how to group the piles into triplets so that your share (the second-largest in each group) is as large as possible.

Why this problem matters

This problem is a textbook example of the "sort then select" greedy pattern. At first glance, the three-way split seems complicated: Alice gets the max, Bob gets the min, and you are stuck in the middle. But once you sort, the optimal grouping becomes obvious. You are effectively choosing which piles to sacrifice to Bob and which to pair with Alice. Problems like Assign Cookies, Boats to Save People, and Advantage Shuffle all rely on this same idea of sorting first and then making greedy pairings.

The key insight

After sorting, you want Bob to take the smallest piles possible, and you want your picks to be as large as possible. The trick: pair each of Bob's piles (the smallest n) with the two largest remaining piles. In each such group, Alice takes the largest and you take the second largest. Since the piles are sorted, this means you skip the first n elements entirely (those go to Bob across all rounds), and then from the remaining 2n elements you take every other one starting from the left (the smaller of each pair), while Alice takes the other.

Concretely: sort the array, skip the first n/3 elements (Bob's), then take every other element from index n onward. The ones you skip in that range go to Alice.

The solution

def max_coins(piles: list[int]) -> int:
    piles.sort()
    n = len(piles) // 3
    total = 0
    for i in range(n, len(piles), 2):
        total += piles[i]
    return total

After sorting in ascending order, the first n elements are the smallest piles. Those are Bob's. From index n to the end, we have 2n elements arranged in ascending order. We take every other element starting at index n (stepping by 2). These are the second-largest values in each implicit group of two. The elements we skip (at odd positions within this range) are Alice's picks, which are always larger than ours. This guarantees we maximize our total.

Visual walkthrough

Complexity analysis

Sorting the array dominates the runtime at O(n log n). The greedy selection pass is O(n). Space is O(1) if you sort in-place (or O(n) if your language creates a copy during sorting).

The building blocks

1. Sort then select

The pattern of sorting an array first, then making a single pass to pick elements according to a rule:

arr.sort()
result = 0
for i in range(start, len(arr), step):
    result += arr[i]

In this problem, you sort and take every other element from a starting offset. In Assign Cookies, you sort both arrays and greedily match the smallest cookie that satisfies each child. In Boats to Save People, you sort and use two pointers to pair the lightest and heaviest person. The core idea is always the same: sorting reveals the optimal pairing structure.

2. Greedy adversarial pairing

The pattern of optimizing your share when other players take predictable portions:

arr.sort()
sacrifice_count = len(arr) // 3
your_picks = arr[sacrifice_count::2]

When you know Alice always takes the max and Bob always takes the min of each group, you control the grouping. The greedy strategy is to sacrifice the smallest elements to Bob and pair the rest so your picks land on the largest possible "second place" values. This adversarial optimization pattern shows up in game theory problems and resource allocation scenarios.

Edge cases

• All piles equal [5, 5, 5, 5, 5, 5]: every group is [5, 5, 5], you always get 5. Total = 5 * n.
• Minimum input [1, 2, 3]: one round. Alice gets 3, you get 2, Bob gets 1. Return 2.
• Already sorted ascending [1, 2, 3, 4, 5, 6, 7, 8, 9]: n = 3. Bob gets [1, 2, 3]. You get piles at indices 3, 5, 7 = 4 + 6 + 8 = 18.
• Already sorted descending [9, 8, 7, 6, 5, 4, 3, 2, 1]: after sorting ascending, same result as above.
• Two distinct values [1, 1, 1, 100, 100, 100]: Bob gets the 1s. Groups are [1, 100, 100] effectively, so you get 100 each round. Total = 200.
• Large n with identical small piles [1, 1, 1, 10, 20, 30]: Bob gets [1, 1]. You get piles at indices 2, 4 = 1 + 20 = 21.

From understanding to recall

You have read the greedy solution and it makes sense. Sort, skip the smallest third, take every other element. Simple. But can you write it from scratch in an interview without looking at it?

The details matter: computing n = len(piles) // 3, starting the loop at index n with step 2, and accumulating those values. These are small details, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the sort-then-select loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize your share from triplet groupings" and the code flows out without hesitation.

The sort-then-select 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 where optimal local choices lead to the global optimum
• Advantage Shuffle - Greedy pairing after sorting to maximize wins against an opponent
• Assign Cookies - Sort-based greedy assignment that shares the same pattern of matching elements optimally

CodeBricks breaks the maximum number of coins you can get LeetCode problem into its sort-then-select and greedy adversarial pairing building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy triplet-picking question shows up in your interview, you do not think about it. You just write it.