The key to this problem is always taking the second largest pile in each sorted triplet to maximize coins. Sort the piles, skip the smallest each time, and accumulate your coins. This strategy ensures that you never pick the smallest pile while maximizing your total, reflecting a clear greedy choice validated by the problem's invariant.
Problem Statement
You are given an array piles of integers where each integer represents the number of coins in a pile. There are 3n piles, and you, Alice, and Bob will take turns choosing piles. In each turn, Alice picks the largest pile, you pick the second largest, and Bob picks the smallest from any three consecutive piles chosen. Your goal is to calculate the maximum number of coins you can collect.
Return the maximum coins you can collect by always choosing optimally under these rules. Consider the effect of ordering the piles and how to select the second largest consistently to ensure your coin total is maximized. The challenge lies in sorting and applying the greedy invariant rather than brute-forcing every possible triplet combination.
Examples
Example 1
Input: piles = [2,4,1,2,7,8]
Output: 9
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 details omitted.
Example 3
Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18
Example details omitted.
Constraints
- 3 <= piles.length <= 105
- piles.length % 3 == 0
- 1 <= piles[i] <= 104
Solution Approach
Sort the Piles Descending
Arrange the array in descending order so that you can consistently access the largest and second largest piles from each group. Sorting is crucial because your choice depends on relative values, and this setup allows for a simple greedy selection.
Pick the Second Largest in Each Triplet
Iterate through the sorted array by skipping the smallest pile each time and summing the second largest. This mirrors the turn sequence of Alice, you, and Bob, ensuring you maximize your coins while leaving the smallest pile to Bob.
Accumulate Coins Efficiently
Use a pointer strategy to traverse the sorted piles: pick your coins from every second largest pile in each set of three, ignoring piles that Bob would take. This keeps the greedy invariant intact and avoids suboptimal selections that reduce your total.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n \cdot \log{}n) |
| Space | O(\log n) |
Sorting takes O(n \cdot \log{}n) and the accumulation loop runs in O(n), giving overall time O(n \cdot \log{}n). Space is O(\log n) for recursion in sorting, making it efficient for up to 10^5 piles.
What Interviewers Usually Probe
- Check if you can always take the second largest pile instead of recomputing each triplet.
- Watch how the invariant of Alice > you > Bob guides greedy selection.
- Consider array length divisibility by three as part of your selection logic.
Common Pitfalls or Variants
Common pitfalls
- Picking the largest pile for yourself instead of the second largest reduces the maximum coins.
- Failing to sort the array before selecting can lead to suboptimal totals.
- Mismanaging the iteration and including Bob's pile in your sum breaks the greedy invariant.
Follow-up variants
- Maximizing coins when only two players pick in order with the same greedy pattern.
- Extending to n players where each must pick in descending priority while maintaining fairness.
- Choosing from piles that are not multiples of three and adjusting the greedy selection accordingly.
How GhostInterview Helps
- GhostInterview highlights the invariant and guides through optimal triplet selection.
- It suggests step-by-step how to skip the smallest pile and sum the second largest for maximum coins.
- Provides visualization of example inputs so you can verify the greedy choice instantly.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy for Maximum Number of Coins You Can Get?
Always pick the second largest pile in each sorted triplet while leaving the smallest pile to Bob to maximize your total coins.
Why is sorting necessary in this coin problem?
Sorting ensures that each triplet is in descending order so the greedy invariant applies, allowing you to consistently pick the optimal pile.
How does the greedy choice plus invariant validation pattern apply?
The pattern ensures you never choose the smallest pile in a triplet and always select the second largest, directly following the turn sequence.
Can this approach handle very large arrays efficiently?
Yes, sorting uses O(n \cdot \log{}n) time and accumulation is O(n), making it efficient for arrays up to 10^5 elements.
What mistakes should be avoided when implementing this problem?
Avoid picking the largest pile for yourself, forgetting to sort, or including Bob's pile in your sum, all of which reduce your maximum coins.
Need direct help with Maximum Number of Coins You Can Get instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Maximum Number of Coins You Can Get from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine the winner in Stone Game VI using a greedy strategy that accounts for each stone's dual value impact on Alice and Bob.
Open problem page#1648 Sell Diminishing-Valued Colored BallsMaximize total value by greedily selling diminishing-valued colored balls based on inventory and customer orders.
Open problem page#1363 Largest Multiple of ThreeFind the largest number divisible by three by selecting and ordering digits optimally using state transition dynamic programming techniques.
Open problem page