There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:
3 piles of coins (not necessarily consecutive).Given an array of integers piles where piles[i] is the number of coins in the ith pile.
Return the maximum number of coins that you can have.
Example 1:
Input: piles = [2,4,1,2,7,8] Output: 9 Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one. Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one. The maximum number of coins which you can have are: 7 + 2 = 9. On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.
Example 2:
Input: piles = [2,4,5] Output: 4
Example 3:
Input: piles = [9,8,7,6,5,1,2,3,4] Output: 18
Constraints:
3 <= piles.length <= 105piles.length % 3 == 01 <= piles[i] <= 104Problem Overview: You are given 3n piles of coins. In every round, three piles are chosen: Alice takes the largest, you take the second largest, and Bob takes the smallest. The goal is to maximize the total number of coins you collect after all piles are used.
Approach 1: Sort and Select Strategy (Greedy with Sorting) (Time: O(n log n), Space: O(1) or O(n) depending on sort)
This problem becomes straightforward once the piles are sorted. After sorting the array in ascending order, the largest pile in each group goes to Alice and the smallest to Bob. You always take the second largest. Instead of simulating three picks every round, iterate from the second-largest position and skip elements strategically. Specifically, start from index n in the sorted array and keep jumping two steps toward the end while summing values. Sorting guarantees that the greedy choice (taking the second largest available pile) produces the maximum total.
The key insight: Bob always removes the smallest pile, which doesn't affect the large values you want. Alice always removes the largest. That leaves you consistently taking the next best option. Sorting simplifies the decision-making process and converts the game into predictable index traversal. This technique commonly appears in greedy problems involving optimal selection after ordering elements.
Approach 2: Maximizing Through Index Analysis (Greedy Observation) (Time: O(n log n), Space: O(1))
Instead of thinking about players picking piles, analyze the pattern of indices after sorting. With 3n piles, exactly n rounds occur. Alice always consumes the largest pile of each triplet, Bob consumes the smallest, and you receive the middle value. After sorting, the piles you obtain correspond to positions starting from len(piles) - 2 and moving left by two steps each round while skipping Bob's piles at the beginning.
Practically, maintain two pointers: one pointing to the largest remaining pile and another implicitly tracking Bob's removals. Each round skips the largest (Alice), adds the next (your pile), and moves past Bob's smallest. This index-based reasoning avoids explicitly grouping triplets and makes the greedy logic clear. The algorithm still depends on sorting, but the index math explains why the greedy strategy is optimal.
The method relies on predictable ordering rather than simulation. Once sorted, the game outcome is fixed. This approach highlights how analyzing index positions in an array can simplify multi-player selection problems.
Recommended for interviews: The greedy sorting approach with index traversal is what interviewers expect. It shows you recognize that the game rules reduce to a deterministic pattern after sorting. Explaining why you always take the second-largest pile demonstrates strong greedy reasoning. A brute-force simulation would work but adds unnecessary complexity, while the sorted greedy approach solves the problem cleanly in O(n log n).
This approach involves sorting the piles of coins first. After sorting, one can consistently select the second largest pile from each group of three piles (Alice's bigger pile, your pile, and Bob's smaller pile) to maximize your coins.
By sorting the piles in descending order, the strategy becomes easier. Alice will always pick the first pile, you will always pick the second pile, and Bob will take the third.
Firstly, we sort the array in descending order using the C standard library's `qsort` function. Then, starting from the second element of the sorted array, we add every second element to our result (since these represent the second largest coin piles in the sorted groups of three).
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.
Another approach, although less direct than sorting, involves analyzing the positions of piles through controlled index manipulation to ensure Alice always takes the maximum pile, you take the second, and Bob takes the least of the three for every set of operations.
Sort the array in descending order. You'll manipulate the index to "skip" the maximum pile (chosen by Alice), select the second, and continue, excluding the least of the three per group chosen by Bob.
Time Complexity: O(n log n) because of sorting the array.
Space Complexity: O(1) as index manipulation happens in place.
| Approach | Complexity |
|---|---|
| Sort and Select Strategy | Time Complexity: O(n log n) due to sorting. |
| Maximizing Through Index Analysis | Time Complexity: O(n log n) because of sorting the array. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Select Strategy | O(n log n) | O(1) or O(n) | General solution; easiest way to implement greedy selection after ordering piles |
| Maximizing Through Index Analysis | O(n log n) | O(1) | When you want to reason about exact indices you receive instead of simulating turns |
Maximum Number of Coins You Can Get | Greedy | 2 Approaches | Leetcode - 1561 • codestorywithMIK • 4,559 views views
Watch 9 more video solutions →Practice Maximum Number of Coins You Can Get with our built-in code editor and test cases.
Practice on FleetCode