Sponsored
Sponsored
This 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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.
1def maxCoins(piles):
2 piles.sort()
3 result = 0
4 n = len(piles) // 3
5 for i in range(n, len(piles), 2):
6 result += piles[i]
7 return result
8
9piles = [2, 4, 1, 2, 7, 8]
10print(maxCoins(piles))We sort the piles array, then iterate through the elements starting from the index n, taking every second element after to sum up to our result.
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.
Time Complexity: O(n log n) because of sorting the array.
Space Complexity: O(1) as index manipulation happens in place.
1
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.