{x}
blog image

Maximum Number of Coins You Can Get

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

Solution Explanation:

This problem can be efficiently solved using a greedy approach combined with sorting. The core idea is that to maximize the number of coins you can get, you should always pick the second largest pile of coins in each round of three. This ensures you consistently get a larger share than Bob.

Algorithm:

  1. Sort: Sort the piles array in ascending order. This step allows us to easily identify the smallest, second largest, and largest piles in each triplet.

  2. Iterate and Accumulate: Iterate through the sorted array starting from the index piles.length / 3. This is because the first piles.length / 3 elements represent the smallest piles, which will be taken by Bob. Increment the index by 2 in each iteration. This skips the largest pile (Alice's choice) and directly selects the second largest pile (your choice).

  3. Sum Coins: Add the value of the second largest pile (the element at the current index) to the ans variable in each iteration.

  4. Return: After the loop completes, return the accumulated ans which represents the maximum number of coins you can get.

Time Complexity Analysis:

  • Sorting the array takes O(n log n) time, where n is the number of piles.
  • Iterating through the sorted array and summing the coins takes O(n) time.

Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity Analysis:

  • In-place sorting algorithms (like those used in most standard libraries) modify the input array directly, requiring only constant extra space. Some sorting algorithms may need O(log n) space depending on the implementation (e.g., recursive mergesort).

Therefore, the space complexity is O(1) or O(log n) depending on the specific sorting implementation used. In practice, it's effectively O(1).

Code Examples:

The code examples provided in various programming languages demonstrate this algorithm effectively. They all follow the same basic steps: sort the array, iterate and pick the second largest from each triplet, and sum the results. The differences lie only in the syntax and specific library functions used for sorting. For example, Python uses piles.sort(), while Java uses Arrays.sort(piles), and C++ uses ranges::sort(piles). Similarly, the loop constructs and indexing vary slightly based on the language's idioms. All achieve the same outcome with the same time and space complexity.