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] <= 104In #1561 Maximum Number of Coins You Can Get, the piles of coins are divided among three players each round. The goal is to maximize the coins you receive while another player always takes the largest pile and the third player takes the smallest. This naturally leads to a greedy strategy.
The key idea is to first sort the array of piles. Once sorted, each round effectively removes three piles: the largest goes to Alice, the second-largest goes to you, and the smallest goes to Bob. By iterating from the end of the sorted array and carefully selecting the second-largest pile in each group of three, you can accumulate the maximum possible coins.
This approach relies on sorting and controlled traversal of the array rather than simulating every choice. The dominant cost comes from sorting the piles, making the solution efficient for large inputs.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) extra space if sorting is done in-place.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Which pile of coins will you never be able to pick up?
Bob is forced to take the last pile of coins, no matter what it is. Which pile should you give to him?
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.
1import java.util.Arrays;
2
3public class MaxCoins {
4 public static int maxCoins(int[] piles) {
5After sorting the array in ascending order, the strategy involves using a loop from the nth (where n is the size/3) position and taking every second element. This is essential after arranging the order the choices were made for Alice (the max).
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#include <vector>
#include <algorithm>
int maxCoins(std::vector<int>& piles) {
std::sort(piles.begin(), piles.end(), std::greater<int>());
int result = 0;
int index = 0;
for (int i = 0; i < piles.size() / 3; ++i) {
index += 2;
result += piles[index];
}
return result;
}
int main() {
std::vector<int> piles = {2, 4, 1, 2, 7, 8};
std::cout << maxCoins(piles) << std::endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting helps organize the piles so the largest, second-largest, and smallest piles are easy to identify. This allows the greedy rule to be applied consistently across all rounds without complicated comparisons.
Yes, this type of greedy and sorting problem is common in coding interviews. It tests your ability to recognize patterns in selection problems and apply a greedy strategy after preprocessing the data.
The optimal approach uses a greedy strategy combined with sorting. After sorting the piles, repeatedly select the second-largest pile from each group of three while ignoring the largest and smallest. This ensures you maximize the number of coins collected each round.
An array is sufficient for this problem. Once the array is sorted, you can traverse it using index pointers to simulate the coin selection process efficiently.
The sorting and index analyses will perform to adjust the pointer to collect coins, skipping what Alice and another skipped by Bob avoids.