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 any3 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.

Examples

Example 1

1
2
3
4
5
6

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

1
2

Input: piles = [2,4,5]
Output: 4

Example 3

1
2

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

Constraints

  • 3 <= piles.length <= 10^5
  • piles.length % 3 == 0
  • 1 <= piles[i] <= 10^4

Solution

Method 1 – Greedy + Sorting

Intuition

To maximize your coins, always let Alice take the largest, you take the second largest, and Bob takes the smallest from each group of 3. By sorting the piles and picking in this order, you maximize your total.

Approach

  1. Sort the piles in ascending order.
  2. For each group of 3 piles (from largest to smallest), let Alice take the largest, you take the second largest, and Bob the smallest.
  3. Start from the end, skip one (Alice), take one (you), skip one (Bob), and repeat for n rounds.
  4. Sum up the coins you take.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int maxCoins(vector<int>& piles) {
        sort(piles.begin(), piles.end());
        int n = piles.size() / 3, ans = 0, j = piles.size() - 2;
        for (int i = 0; i < n; ++i, j -= 2) ans += piles[j];
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

import "sort"
func maxCoins(piles []int) int {
    sort.Ints(piles)
    n, ans, j := len(piles)/3, 0, len(piles)-2
    for i := 0; i < n; i, j = i+1, j-2 {
        ans += piles[j]
    }
    return ans
}
1
2
3
4
5
6
7
8
9

import java.util.*;
class Solution {
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int n = piles.length / 3, ans = 0, j = piles.length - 2;
        for (int i = 0; i < n; i++, j -= 2) ans += piles[j];
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun maxCoins(piles: IntArray): Int {
        piles.sort()
        var ans = 0
        var j = piles.size - 2
        repeat(piles.size / 3) {
            ans += piles[j]
            j -= 2
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def maxCoins(self, piles: list[int]) -> int:
        piles.sort()
        ans = 0
        j = len(piles) - 2
        for _ in range(len(piles)//3):
            ans += piles[j]
            j -= 2
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn max_coins(mut piles: Vec<i32>) -> i32 {
        piles.sort();
        let mut ans = 0;
        let mut j = piles.len() - 2;
        for _ in 0..(piles.len()/3) {
            ans += piles[j];
            j -= 2;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    maxCoins(piles: number[]): number {
        piles.sort((a, b) => a - b);
        let ans = 0, j = piles.length - 2;
        for (let i = 0; i < piles.length / 3; i++, j -= 2) {
            ans += piles[j];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the piles.
  • 🧺 Space complexity: O(1) (ignoring the sort’s internal space), as we use only a few variables for computation.