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.
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; }}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.