#1561 Maximum Number of Coins You Can Get - Solution

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 3 piles 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 i^th 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: 4

Example 3:

Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18

Constraints:

3 <= piles.length <= 10⁵
piles.length % 3 == 0
1 <= piles[i] <= 10⁴

In #1561 Maximum Number of Coins You Can Get, the piles of coins are divided among three players each round. The goal is to maximize the coins you receive while another player always takes the largest pile and the third player takes the smallest. This naturally leads to a greedy strategy.

The key idea is to first sort the array of piles. Once sorted, each round effectively removes three piles: the largest goes to Alice, the second-largest goes to you, and the smallest goes to Bob. By iterating from the end of the sorted array and carefully selecting the second-largest pile in each group of three, you can accumulate the maximum possible coins.

This approach relies on sorting and controlled traversal of the array rather than simulating every choice. The dominant cost comes from sorting the piles, making the solution efficient for large inputs.

Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) extra space if sorting is done in-place.

Approach	Time Complexity	Space Complexity
Greedy with Sorting	O(n log n)	O(1)

Solutions (12)

Sort and Select Strategy

This approach involves sorting the piles of coins first. After sorting, one can consistently select the second largest pile from each group of three piles (Alice's bigger pile, your pile, and Bob's smaller pile) to maximize your coins.

By sorting the piles in descending order, the strategy becomes easier. Alice will always pick the first pile, you will always pick the second pile, and Bob will take the third.

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.

C C++Java Python C#JavaScript

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int maxCoins(std::vector<int>& piles) {
6    std::sort(piles.begin(), piles.end(), std::greater<int>());
7    int result = 0;
8    for (int i = 1, j = piles.size() - 1; i < j; i += 2, --j) {
9        result += piles[i];
10    }
11    return result;
12}
13
14int main() {
    std::vector<int> piles = {2, 4, 1, 2, 7, 8};
    std::cout << maxCoins(piles) << std::endl;
    return 0;
}

Explanation

The vector is sorted in descending order and a loop is used to accumulate your coins by picking the second pile each time. Sorting ensures that Alice gets the max, you get the second max, and Bob gets the minimum of the three choices.

Maximizing Through Index Analysis

Another approach, although less direct than sorting, involves analyzing the positions of piles through controlled index manipulation to ensure Alice always takes the maximum pile, you take the second, and Bob takes the least of the three for every set of operations.

Time Complexity: O(n log n) because of sorting the array.
Space Complexity: O(1) as index manipulation happens in place.

C C++Java Python C#JavaScript

1using System.Linq;

public class Solution {
    public int MaxCoins(int[] piles) {
        Array.Sort(piles);
        int result = 0;
        int index = piles.Length - 2;
        for (int i = 0; i < piles.Length / 3; i++) {
            result += piles[index];
            index -= 2;
        }
        return result;
    }
    public static void Main() {
        int[] piles = new int[] {2, 4, 1, 2, 7, 8};
        Solution sol = new Solution();
        Console.WriteLine(sol.MaxCoins(piles));
    }
}