We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Coins You Can Get

Number: 1683

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of piles of coins where the number of piles is a multiple of 3, you and two friends (Alice and Bob) select coins from triplets of piles in each step. For each triplet you pick:

  • You choose any 3 piles.
  • Alice takes the pile with the maximum coins.
  • You take the next pile with the maximum coins.
  • Bob takes the remaining pile.

Your goal is to maximize the total number of coins you can get. Return the maximum coins you can accumulate with optimal selection.

Key Insights

  • Sorting the array helps structure the optimal grouping.
  • In any group of three sorted piles, giving Alice the largest pile means you pick the second-largest.
  • By sorting and then picking appropriately from the upper portion of the list, you can maximize your sum.
  • The optimal strategy is to ensure that the biggest piles go to Alice and then for every triplet, you secure the next largest coin count.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array.
Space Complexity: O(1) if the sort is in-place; otherwise, O(n) additional space might be needed depending on the sorting algorithm.

Solution

The approach is based on a greedy strategy:

  1. Sort the piles in ascending order.
  2. Notice that if you partition the sorted array into triplets optimally, Alice will always take the largest coin in each triplet.
  3. To maximize your coins, you want to secure the second largest coin from each valid triplet.
  4. By choosing triplets in a way that the larger numbers are paired with smaller ones, you can guarantee that you get a good share.
  5. A known method after sorting is to sum the coin values from a specific set of indices: start from the element just before the largest and then skip every other element. In other words, sum the elements at positions len(piles)-2, len(piles)-4, ..., until you have taken n coins (where n = piles.length / 3).

This works because:

  • The sorted order groups coins optimally.
  • The largest coins are allocated to Alice, so your optimal coins are the coin values just next to the largest ones in each triplet.

Code Solutions

# Python implementation
def maxCoins(piles):
    # Sort the piles in ascending order
    piles.sort()
    total_coins = 0
    n = len(piles) // 3  # number of groups
    # Start from the second largest (index: len(piles)-2) and pick every second coin
    for i in range(n):
        # Element index calculated from the end: use -2 - 2*i
        total_coins += piles[-2 - 2*i]
    return total_coins

# Example usage:
# piles = [2,4,1,2,7,8]
# print(maxCoins(piles))  # Output: 9
← Back to All Questions