Maximum Number of Coins You Can Get

Share

Split piles of coins into groups of 3: Alice gets max, you get second, Bob gets min. Maximize your coins.

Example 1
Input: piles=[2,4,1,2,7,8] → Output: 9. Split into (1,2,4) and (2,7,8). You get 2+7=9.
Example 2
Input: piles=[2,4,5] → Output: 4

Solution Approach

Sort piles. In each triplet (from sorted), you always take second largest. Bob takes the smallest pile.

  • Sort piles
  • Bob takes first n/3 piles (smallest)
  • You take every other pile from position n/3: indices n/3, n/3+2, n/3+4...
  • Sum your piles
Java
public int maxCoins(int[] piles) {
    Arrays.sort(piles);
    int n = piles.length, sum = 0;
    for (int i = n / 3; i < n; i += 2) sum += piles[i];
    return sum;
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(1)