Maximum Number of Coins You Can Get
MedPrompt
There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:
- In each step, you will choose any
3piles of coins (not necessarily consecutive). - Of your choice, Alice will pick the pile with the maximum number of coins.
- You will pick the next pile with the maximum number of coins.
- Your friend Bob will pick the last pile.
- Repeat until there are no more piles of coins.
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: 4Example 3:
Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18
Constraints:
3 <= piles.length <= 105piles.length % 3 == 01 <= piles[i] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach attempts to solve the problem by exploring every possible way to form the triplets. It uses recursion and backtracking to generate all valid groupings of n triplets from the 3n piles. For each complete grouping, it calculates the sum of coins you would receive and keeps track of the maximum sum found across all groupings.
Algorithm
- Define a recursive function, say
findMaxCoins(available_piles, current_sum). - The base case for the recursion is when
available_pilesis empty. At this point, we comparecurrent_sumwith a global maximum and update it if necessary. - In the recursive step, iterate through all possible combinations of choosing 3 piles from the
available_piles. - For each chosen triplet, sort it to identify the largest pile (for Alice), the second-largest (for you), and the smallest (for Bob).
- Add the value of your pile to
current_sumand make a recursive call with the remaining piles. - This process explores the entire search space of forming triplets to find the one that maximizes your total coins.
Walkthrough
The brute-force method involves a recursive exploration of all partitions of the piles array into n triplets. A helper function would take the set of remaining piles as an argument. In each call, it would try picking every possible set of three piles, assign them according to the rules (Alice gets max, you get second max, Bob gets min), and then recursively call itself with the rest of the piles. The value from your pile is added to the sum for that path. The base case is when no piles are left. The maximum sum found among all recursive paths is the answer. However, the number of ways to partition 3n items into n groups of 3 is given by the formula (3n)! / (n! * (3!)^n), which grows astronomically, making this approach computationally infeasible for the given constraints.
Complexity
Time
Exponential, roughly O((3n)!). This is far too slow for the given constraints and is only a theoretical approach.
Space
O(N), where N is the number of piles. This is for the recursion stack depth and to store the state of available piles at each step.
Trade-offs
Pros
Conceptually straightforward as it directly models the problem statement by trying all possibilities.
Cons
Extremely inefficient and will time out on all but the smallest inputs.
Complex to implement correctly due to the management of combinations and recursive states.
A much more efficient method is to use a greedy strategy. The core insight is that to maximize your total coins, you should always try to pick the largest possible pile available to you in each turn. Since you always get the second-largest pile of a chosen triplet, the optimal strategy involves pairing the largest available piles together.
Algorithm
- Sort the
pilesarray in non-decreasing order. - Initialize a variable
my_coinsto 0. - Determine the number of triplets to be formed,
n = piles.length / 3. - The piles you will receive are the second-largest in each of the
noptimally chosen triplets. These correspond to the piles at indicespiles.length - 2,piles.length - 4, ..., down to indexnin the sorted array. - Iterate from
i = piles.length - 2down tonwith a step of -2, and addpiles[i]tomy_coins. - Return
my_coins.
Walkthrough
By sorting the piles array, we can easily identify the smallest, middle, and largest piles. Let the sorted array be s. To maximize your share, you should aim to get the largest possible second-place piles. The best strategy is to form triplets by taking the largest available pile for Alice, the second-largest for yourself, and the smallest available for Bob. This maximizes your immediate gain while saving larger piles for your future turns by giving the absolute smallest piles to Bob.
This translates to the following selection process:
- Triplet 1: Alice takes
s[3n-1], you takes[3n-2], Bob takess[0]. - Triplet 2: Alice takes
s[3n-3], you takes[3n-4], Bob takess[1]. ...and so on forntriplets.
Summing up your piles (s[3n-2], s[3n-4], etc.) gives the maximum possible total.
import java.util.Arrays; class Solution { public int maxCoins(int[] piles) { Arrays.sort(piles); int myCoins = 0; int n = piles.length / 3; // My choices are the second pile from the end in each triplet selection for (int i = piles.length - 2; i >= n; i -= 2) { myCoins += piles[i]; } return myCoins; }}Complexity
Time
O(N log N), where N is the number of piles. The complexity is dominated by the sorting step.
Space
O(log N) or O(N), depending on the sort algorithm's implementation. Java's `Arrays.sort` for primitive types has an average space complexity of O(log N).
Trade-offs
Pros
Significantly more efficient than brute force.
Relatively simple to understand and implement.
Works for any range of input values.
Cons
The O(N log N) time complexity might be suboptimal if the range of values in
pilesis small.
This approach uses the same greedy logic as the sorting method but optimizes the process by leveraging the fact that the coin values are within a limited range. Instead of a comparison-based sort, it uses a counting mechanism (similar to a counting sort) to find the required piles in linear time relative to the number of piles and the range of their values.
Algorithm
- Create a frequency array,
counts, of a size based on the maximum possible value of a pile (e.g., 10001 based on constraints). - Iterate through the input
pilesand populate thecountsarray. This takes O(N) time. - Initialize
my_coins = 0,n = piles.length / 3. - Use two pointers:
small_ptrstarting from 1 andlarge_ptrstarting from the maximum value. - Loop
ntimes to simulate pickingntriplets:- Find Alice's pile: Move
large_ptrdownwards until a non-zero count is found (counts[large_ptr] > 0). Decrement the count. - Find your pile: Again, move
large_ptrdownwards to find the next available largest pile. Add this value tomy_coinsand decrement its count. - Find Bob's pile: Move
small_ptrupwards until a non-zero count is found. Decrement its count.
- Find Alice's pile: Move
- Return
my_coins.
Walkthrough
We can avoid the O(N log N) sorting cost by first counting the occurrences of each pile size. Since the constraints state 1 <= piles[i] <= 10000, we can use a frequency array of size 10001. After populating this frequency map in O(N) time, we can simulate the greedy selection process. We maintain two pointers, one for the largest available pile values (large_ptr) and one for the smallest (small_ptr). In a loop that runs n times, we pick piles for Alice, you, and Bob by adjusting these pointers and decrementing the counts in the frequency array. This allows us to find the required piles without a full sort.
class Solution { public int maxCoins(int[] piles) { int maxVal = 0; for (int p : piles) { if (p > maxVal) { maxVal = p; } } int[] counts = new int[maxVal + 1]; for (int p : piles) { counts[p]++; } int myCoins = 0; int n = piles.length / 3; int smallPtr = 1; int largePtr = maxVal; for (int i = 0; i < n; i++) { // Alice's turn: take the largest available while (counts[largePtr] == 0) { largePtr--; } counts[largePtr]--; // My turn: take the next largest available while (counts[largePtr] == 0) { largePtr--; } myCoins += largePtr; counts[largePtr]--; // Bob's turn: take the smallest available while (counts[smallPtr] == 0) { smallPtr++; } counts[smallPtr]--; } return myCoins; }}Complexity
Time
O(N + K), where N is the number of piles and K is the maximum value. This is faster than O(N log N) for the given constraints.
Space
O(K), where K is the maximum possible value in `piles`. This is for the frequency array.
Trade-offs
Pros
More efficient than the sorting approach, with a linear time complexity.
Optimal solution given the problem constraints.
Cons
Requires extra space proportional to the maximum possible pile value (K), which could be large if the values are not constrained.
Slightly more complex to implement than the sorting approach.
Solutions
Solution
class Solution {public int maxCoins(int[] piles) { Arrays.sort(piles); int ans = 0; for (int i = piles.length - 2; i >= piles.length / 3; i -= 2) { ans += piles[i]; } return ans; }}class Solution {public: int maxCoins(vector<int> &piles) { sort(piles.begin(), piles.end()); int ans = 0; for (int i = piles.size() - 2; i >= (int)piles.size() / 3; i -= 2) ans += piles[i]; return ans; }};class Solution: def maxCoins(self, piles: List[int]) -> int: piles . sort() return sum(piles[- 2: len(piles) // 3 - 1: - 2])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.