# Maximum Number of Coins You Can Get
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-coins-you-can-get)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-coins-you-can-get
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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 `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:** 4

**Example 3:**

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

**Constraints:**

* `3 <= piles.length <= 105`
* `piles.length % 3 == 0`
* `1 <= piles[i] <= 104`

# Approaches
## Brute Force with Backtracking
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.
**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.
**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.
### Explanation
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.
### Algorithm
- Define a recursive function, say `findMaxCoins(available_piles, current_sum)`.
- The base case for the recursion is when `available_piles` is empty. At this point, we compare `current_sum` with 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_sum` and 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.

## Greedy Approach with Sorting
A much more efficient method is to use a greedy strategy. The core insight is that to maximize your total coins, you should always try to pick the largest possible pile available to you in each turn. Since you always get the second-largest pile of a chosen triplet, the optimal strategy involves pairing the largest available piles together.
**Time:** O(N log N), where N is the number of piles. The complexity is dominated by the sorting step. · **Space:** O(log N) or O(N), depending on the sort algorithm's implementation. Java's `Arrays.sort` for primitive types has an average space complexity of O(log N).
**Pros:** Significantly more efficient than brute force.; Relatively simple to understand and implement.; Works for any range of input values.
**Cons:** The O(N log N) time complexity might be suboptimal if the range of values in `piles` is small.
### Explanation
By sorting the `piles` array, we can easily identify the smallest, middle, and largest piles. Let the sorted array be `s`. To maximize your share, you should aim to get the largest possible second-place piles. The best strategy is to form triplets by taking the largest available pile for Alice, the second-largest for yourself, and the smallest available for Bob. This maximizes your immediate gain while saving larger piles for your future turns by giving the absolute smallest piles to Bob.

This translates to the following selection process:
1. Triplet 1: Alice takes `s[3n-1]`, you take `s[3n-2]`, Bob takes `s[0]`.
2. Triplet 2: Alice takes `s[3n-3]`, you take `s[3n-4]`, Bob takes `s[1]`.
...and so on for `n` triplets.

Summing up your piles (`s[3n-2]`, `s[3n-4]`, etc.) gives the maximum possible total.

```java
import java.util.Arrays;

class Solution {
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int myCoins = 0;
        int n = piles.length / 3;
        // My choices are the second pile from the end in each triplet selection
        for (int i = piles.length - 2; i >= n; i -= 2) {
            myCoins += piles[i];
        }
        return myCoins;
    }
}
```
### Algorithm
- Sort the `piles` array in non-decreasing order.
- Initialize a variable `my_coins` to 0.
- Determine the number of triplets to be formed, `n = piles.length / 3`.
- The piles you will receive are the second-largest in each of the `n` optimally chosen triplets. These correspond to the piles at indices `piles.length - 2`, `piles.length - 4`, ..., down to index `n` in the sorted array.
- Iterate from `i = piles.length - 2` down to `n` with a step of -2, and add `piles[i]` to `my_coins`.
- Return `my_coins`.

## Optimized Greedy Approach using Counting
This approach uses the same greedy logic as the sorting method but optimizes the process by leveraging the fact that the coin values are within a limited range. Instead of a comparison-based sort, it uses a counting mechanism (similar to a counting sort) to find the required piles in linear time relative to the number of piles and the range of their values.
**Time:** O(N + K), where N is the number of piles and K is the maximum value. This is faster than O(N log N) for the given constraints. · **Space:** O(K), where K is the maximum possible value in `piles`. This is for the frequency array.
**Pros:** More efficient than the sorting approach, with a linear time complexity.; Optimal solution given the problem constraints.
**Cons:** Requires extra space proportional to the maximum possible pile value (K), which could be large if the values are not constrained.; Slightly more complex to implement than the sorting approach.
### Explanation
We can avoid the `O(N log N)` sorting cost by first counting the occurrences of each pile size. Since the constraints state `1 <= piles[i] <= 10000`, we can use a frequency array of size 10001. After populating this frequency map in `O(N)` time, we can simulate the greedy selection process. We maintain two pointers, one for the largest available pile values (`large_ptr`) and one for the smallest (`small_ptr`). In a loop that runs `n` times, we pick piles for Alice, you, and Bob by adjusting these pointers and decrementing the counts in the frequency array. This allows us to find the required piles without a full sort.

```java
class Solution {
    public int maxCoins(int[] piles) {
        int maxVal = 0;
        for (int p : piles) {
            if (p > maxVal) {
                maxVal = p;
            }
        }
        
        int[] counts = new int[maxVal + 1];
        for (int p : piles) {
            counts[p]++;
        }
        
        int myCoins = 0;
        int n = piles.length / 3;
        int smallPtr = 1;
        int largePtr = maxVal;
        
        for (int i = 0; i < n; i++) {
            // Alice's turn: take the largest available
            while (counts[largePtr] == 0) {
                largePtr--;
            }
            counts[largePtr]--;
            
            // My turn: take the next largest available
            while (counts[largePtr] == 0) {
                largePtr--;
            }
            myCoins += largePtr;
            counts[largePtr]--;
            
            // Bob's turn: take the smallest available
            while (counts[smallPtr] == 0) {
                smallPtr++;
            }
            counts[smallPtr]--;
        }
        
        return myCoins;
    }
}
```
### Algorithm
- Create a frequency array, `counts`, of a size based on the maximum possible value of a pile (e.g., 10001 based on constraints).
- Iterate through the input `piles` and populate the `counts` array. This takes O(N) time.
- Initialize `my_coins = 0`, `n = piles.length / 3`.
- Use two pointers: `small_ptr` starting from 1 and `large_ptr` starting from the maximum value.
- Loop `n` times to simulate picking `n` triplets:
  - Find Alice's pile: Move `large_ptr` downwards until a non-zero count is found (`counts[large_ptr] > 0`). Decrement the count.
  - Find your pile: Again, move `large_ptr` downwards to find the next available largest pile. Add this value to `my_coins` and decrement its count.
  - Find Bob's pile: Move `small_ptr` upwards until a non-zero count is found. Decrement its count.
- Return `my_coins`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxCoins(vector<int> &piles) {
    sort(piles.begin(), piles.end());
    int ans = 0;
    for (int i = piles.size() - 2; i >= (int)piles.size() / 3; i -= 2)
      ans += piles[i];
    return ans;
  }
};

```

### Python

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

```