Maximum Number of Coins You Can Get — Solution

Problem

You have 3n piles of coins to distribute across three people. Each round, you choose any three piles: your greedy friend Alice always takes the largest, your other friend Bob takes the smallest, and you keep the middle pile. After n rounds all piles are gone. Maximize the total coins you collect.

• Input: piles = [2, 4, 1, 2, 7, 8]
• Output: 9
• Explanation: Take triple (1, 7, 8) — you keep 7; take triple (2, 2, 4) — you keep 2; total = 9.

A suboptimal triple like (1, 2, 8) gives you only 2 while "wasting" 8 on Alice and 1 on Bob — you want Alice to take a pile that is barely larger than yours.

Intuition

Alice always takes the maximum of any triple you form, so you will never get the single largest pile. The best you can do each round is the second-largest. To maximize globally, you want Bob's required minimums to be as cheap as possible — give him the n smallest piles outright. Among the remaining 2n piles, pairing adjacent elements ensures Alice "steals" as little as possible above what you keep: she takes 9 while you keep 8, rather than her taking 9 while you keep 1.

Solution — Greedy Sort

Sort all piles ascending. Bob takes the bottom n (the cheapest wasted coins). The remaining 2n piles are split into n adjacent pairs, and you keep the lower of each pair. Reading off every other pile starting at index n gives your optimal total.

1. Sort piles in ascending order.
2. Let n = len(piles) // 3 — the number of rounds.
3. The bottom n piles (indices 0 through n−1) go to Bob; skip them entirely.
4. From index n onward, take every other pile: indices n, n+2, n+4, …, 3n−2.
5. Return the sum of those n values.

1class Solution:
2    def maxCoins(self, piles: List[int]) -> int:
3        piles.sort()
4        n = len(piles) // 3  # number of rounds; Bob absorbs the n smallest piles
5        return sum(piles[n::2])  # every other pile from index n; Alice always gets the one we skip

Time: O(n log n) — dominated by sorting; the single-pass accumulation is O(n). Space: O(1) — sorting is in-place; no extra data structures needed.

Complexity Summary

Common Mistakes

• Greedily picking the three largest piles each round: always pulling the top 3 gives you the second-highest of those three but misses a better global split. On [1,2,3,4,5,6,7,8,9], this yields 8+5+2=15; the optimal is 8+6+4=18 by spreading Bob's burden across the small end.
• Off-by-one: using piles[n+1::2] instead of piles[n::2]: shifting the start by one puts you on Alice's positions, so you collect her coins and skip your own.
• Confusing n with len(piles): the problem has 3n total piles; n (the number of rounds) is len(piles) // 3, not len(piles).
• Pairing non-adjacent piles in the top 2n: pairing pile at index 3n−1 (largest) with pile at index n (smallest of the top 2n) forces Alice to take 3n−1 while you get only n — pairing adjacent (3n−2, 3n−1) instead costs Alice the same top pile but earns you the much better 3n−2.
• Skipping the sort: without sorting you cannot tell which n piles Bob should absorb or which positions correspond to your take vs Alice's, making the index-stepping formula meaningless.

Related Problems

• boats-to-save-people — sort then pair lightest with heaviest greedily; same "sort unlocks the pairing pattern" insight
• candy — greedy distribution where satisfying constraints forces you to assign the minimum at each position
• kth-largest-element-in-an-array — sort and select by absolute position; same "sorted index = identity" idea
• gas-station — greedy choice about which positions to start from under global constraints
• largest-number — custom sort defines the globally optimal ordering, same theme of "the right comparator makes the answer fall out"