Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1561. Maximum Number of Coins You Can Get - Leetcode Solution

Code Implementation

class Solution:
    def maxCoins(self, piles):
        piles.sort()
        n = len(piles) // 3
        res = 0
        # Start from the second largest in each group of 3
        for i in range(n, len(piles), 2):
            res += piles[i]
        return res
      
class Solution {
public:
    int maxCoins(vector<int>& piles) {
        sort(piles.begin(), piles.end());
        int n = piles.size() / 3;
        int res = 0;
        for (int i = n; i < piles.size(); i += 2) {
            res += piles[i];
        }
        return res;
    }
};
      
import java.util.*;
class Solution {
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int n = piles.length / 3;
        int res = 0;
        for (int i = n; i < piles.length; i += 2) {
            res += piles[i];
        }
        return res;
    }
}
      
var maxCoins = function(piles) {
    piles.sort((a, b) => a - b);
    let n = Math.floor(piles.length / 3);
    let res = 0;
    for (let i = n; i < piles.length; i += 2) {
        res += piles[i];
    }
    return res;
};

Problem Description

You are given an array piles of 3n integers, representing piles of coins. You are playing a game with two friends (Alice and Bob). Each round, all three of you take turns choosing one pile each:
  • Alice always picks the pile with the most coins.
  • You always pick the next highest pile.
  • Bob always gets the remaining pile (the smallest of the three).
This process repeats until there are no more piles left. Your goal is to maximize the total number of coins you can collect.
Constraints:
  • Each pile can only be chosen once.
  • The number of piles is always a multiple of 3.
  • There is only one valid way to play the game as described above.
Return the maximum number of coins you can get.

Thought Process

At first glance, it might seem like you need to simulate every round, keeping track of who picks which pile. Brute-forcing all possible combinations would be too slow, especially for large arrays.

However, since the picking order is fixed (Alice always gets the biggest, you get the next, Bob gets the smallest), we can look for a pattern or shortcut. If we sort the piles, we can easily simulate the picking process: Alice always takes the largest, you take the second largest, and Bob the smallest from each group of three.

The key insight is that to maximize your coins, you should always take the second largest pile in every group of three, after Alice picks the largest.

Solution Approach

Let's break down the steps:
  1. Sort the array: Sorting piles in ascending order makes it easy to pick the largest, second largest, and smallest in each round.
  2. Divide into groups: Since there are 3n piles, we can think of the sorted array as n groups of three piles each.
  3. Simulate picking:
    • In each group, Alice picks the largest (the last element in the group), you pick the second largest (the middle element), and Bob gets the smallest (the first).
    • But since all piles are sorted together, we can simulate this by always letting you pick the second largest pile from each set, starting from the nth element and skipping every other pile (because Alice gets the largest, you the next, Bob the smallest, and so on).
  4. Sum your picks: Add up all the piles you would pick following this pattern.
Why does this work? Sorting ensures the biggest coins go to Alice, the next biggest to you, and the smallest to Bob in each round. By always picking the second largest from the remaining piles, you maximize your total.

Example Walkthrough

Example Input: piles = [2,4,1,2,7,8]

Step 1: Sort the array
Sorted piles: [1,2,2,4,7,8]

Step 2: Group into rounds
There are 6 piles, so 2 rounds (n=2):
  • Round 1: [1, 2, 2]
  • Round 2: [4, 7, 8]
Step 3: Picking order in each round
  • Alice: picks 2 (largest in first group), then 8 (largest in second group)
  • You: pick 2 (second largest in first group), then 7 (second largest in second group)
  • Bob: picks 1 and 4 (smallest in each group)
Step 4: Sum your coins
You get 2 + 7 = 9 coins.

Time and Space Complexity

Brute-force approach:
  • Would involve simulating all possible picking orders, which is factorial time and completely infeasible for large piles.
Optimized approach:
  • Time Complexity: O(n log n) because sorting the array dominates the runtime. The subsequent loop is O(n).
  • Space Complexity: O(1) extra space (if sorting in-place), or O(n) if sorting creates a new array.

Summary

By sorting the piles and always picking the second largest in each round, you efficiently maximize your coins. The insight is recognizing the fixed picking order and leveraging sorting to simulate the process. This approach is both elegant and efficient, reducing the problem to a simple loop after sorting.