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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Coins You Can Get

Difficulty: Medium

Problem Description

Given an array of integers piles where piles[i] is the number of coins in the i-th pile, you and your friends will take piles of coins as follows: In each step, you will choose any 3 piles of coins, Alice will pick the pile with the maximum number of coins, you will pick the next pile with the maximum number of coins, and your friend Bob will pick the last pile. Return the maximum number of coins that you can have.

Key Insights

  • You need to maximize the coins you collect while minimizing what Alice and Bob can take.
  • Sorting the piles helps in determining the best triplet to choose in each round.
  • The strategy is to always take the second largest from the selected triplet to maximize your total coins.
  • Only consider the n largest piles for your collection since you will be making n selections.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the piles. Space Complexity: O(1) - we are using constant space for calculations.

Solution

The solution involves sorting the piles array to ensure that we can easily access the largest and second-largest piles. After sorting, we will select triplets from the last 3n piles, choosing the triplet such that we always collect the second largest pile in each selection. This greedy approach guarantees that you maximize your coins.

Code Solutions

def maxCoins(piles):
    # Sort the piles in ascending order
    piles.sort()
    total_coins = 0
    n = len(piles) // 3  # Calculate how many selections we can make

    # Iterate backwards to select piles
    for i in range(n):
        # Select the second largest pile from the triplet
        total_coins += piles[-(2 + i)]  # Picking the second largest
    return total_coins
← Back to All Questions