There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:
3 piles of coins (not necessarily consecutive).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 <= 105piles.length % 3 == 01 <= piles[i] <= 104This approach involves sorting the piles of coins first. After sorting, one can consistently select the second largest pile from each group of three piles (Alice's bigger pile, your pile, and Bob's smaller pile) to maximize your coins.
By sorting the piles in descending order, the strategy becomes easier. Alice will always pick the first pile, you will always pick the second pile, and Bob will take the third.
Firstly, we sort the array in descending order using the C standard library's `qsort` function. Then, starting from the second element of the sorted array, we add every second element to our result (since these represent the second largest coin piles in the sorted groups of three).
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.
Another approach, although less direct than sorting, involves analyzing the positions of piles through controlled index manipulation to ensure Alice always takes the maximum pile, you take the second, and Bob takes the least of the three for every set of operations.
Sort the array in descending order. You'll manipulate the index to "skip" the maximum pile (chosen by Alice), select the second, and continue, excluding the least of the three per group chosen by Bob.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) because of sorting the array.
Space Complexity: O(1) as index manipulation happens in place.
| Approach | Complexity |
|---|---|
| Sort and Select Strategy | Time Complexity: O(n log n) due to sorting. |
| Maximizing Through Index Analysis | Time Complexity: O(n log n) because of sorting the array. |
Coin Change - Dynamic Programming Bottom Up - Leetcode 322 • NeetCode • 574,201 views views
Watch 9 more video solutions →Practice Maximum Number of Coins You Can Get with our built-in code editor and test cases.
Practice on FleetCode