#1561

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Number of Coins You Can Get

Solve the Maximum Number of Coins You Can Get using greedy pile selection and invariant validation to maximize your coins efficiently.

array math greedy sorting game theory

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.

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.

terminal

Solution

Solution 1: Greedy + Sorting

To maximize the number of coins we get, we can greedily let Bob take the smallest $n$ piles of coins. Each time, we let Alice take the largest pile of coins, then we take the second largest pile of coins, and so on, until there are no more coins to take.

1

2

3

4

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles.sort()
        return sum(piles[len(piles) // 3 :][::2])

Continue Practicing

#1686 stone game vi #1648 sell diminishing valued colored balls #1363 largest multiple of three