1561. Maximum Number of Coins You Can Get
Problem Description
In this problem, we have 3n
piles of coins of different sizes, which means the total number of piles is divisible by 3. You are playing a game with two other friends, Alice and Bob. You will take turns choosing any 3 piles of coins. During each turn:
- Alice will always take the pile with the largest number of coins.
- You will take the next largest pile.
- Bob will take the pile with the smallest number of coins.
This process repeats until there are no more piles left. Your objective is to maximize the number of coins you get by the end of the game. The question provides us with an array of integers piles
, where piles[i]
represents the number of coins in the i-th
pile, and we need to return the maximum coins you can get under the game's rules.
Intuition
The intuition behind the solution is to use a greedy approach. A greedy algorithm is one that always makes the choice that looks best at the moment without considering the future outcomes. Applying this to our scenario, since Alice will always take the largest pile and Bob the smallest, the best strategy for you is to ensure that each time you choose 3 piles, the second largest pile is as large as possible, without ever being the largest.
To ensure that, the best approach is to sort the piles in ascending order. By doing so, we can then pair the largest available pile for Alice with the next largest pile for ourselves, which leaves the smallest pile in this subset for Bob. By choosing from the larger end of the sorted piles, we can maximize the coins we get.
After sorting the piles, we can iterate through the sorted array taking the second largest element from the end in each step until we have picked n
piles ourselves. To do so:
- We start from the second element from the end, as this would have been the largest pile if we picked any three piles.
- We move two steps towards the front of the array each time to ensure we are always picking the next pile with the maximum number of coins available for us.
- We stop picking after we have selected
n
piles for ourselves, which happens aftern
iterations as there are3n
piles and we are picking one out of every three piles.
Therefore, the sum of the selected piles would give us the maximum coins we can have.
Solution Approach
The solution to this problem leverages the sort
function to order the array of piles and then accumulate the coins that you would receive according to the rules established by the game.
Here is a step-by-step breakdown of the implementation:
-
Sorting the Piles: First, we use Python's built-in sort function
piles.sort()
which sorts the array of piles in ascending order. Sorting is a common pre-processing step in greedy algorithms. No additional data structure is used here; the array is sorted in place. -
Slicing the Sorted Piles: After sorting, the largest piles are at the end of the array. By employing Python's slicing, we can get every other pile starting from the second-to-last element using the slice
piles[-2 : len(piles) // 3 - 1 : -2]
.piles[-2]
is the starting point, which represents the second largest pile because the largest pile would be taken by Alice.len(piles) // 3 - 1
is the stopping point, which ensures that only the piles meant for you are included, leaving out the smallest third of the piles, which are meant for Bob.:-2
is the step, which allows us to skip every alternate pile to simulate the take turns in which you would always end up with the second largest pile out of every chosen set of three piles.
-
Summation: Lastly, we apply the
sum()
function on the sliced array to get the total number of coins accumulated across all chosen piles. This sum represents the maximum number of coins you can obtain by following this strategy.
The algorithm exhibits a greedy property since in every turn, it picks the local optimum (the second biggest pile of every chosen set of three piles) without considering the rest of the array. This local optimum choice leads to a global optimum, which is the maximum number of coins you can achieve.
The complexity of this algorithm is primarily determined by the sorting step. Python's sort function has a time complexity of O(n log n). The slicing step is O(n), where n
is the total number of piles divided by 3, since we're summing every second pile out of the two-thirds of the piles. So, the overall time complexity is dominated by the sorting step, making it O(n log n).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach.
Assume we have an array of piles piles = [2, 4, 1, 2, 7, 8]
. There are 3n = 6
piles, which implies that n = 2
. According to the rules, Alice will choose the largest pile, you will choose the second-largest pile, and Bob will choose the smallest pile each turn.
Here is how you can follow the steps outlined in the solution approach:
-
Sorting the Piles: First, sort
piles
to get[1, 2, 2, 4, 7, 8]
. -
Slicing the Sorted Piles: To simulate taking turns:
- Start from the second-to-last element to avoid the largest pile, which Alice takes. This gives us a starting point of
piles[-2]
, which is7
. - End at
len(piles) // 3 - 1
which is1
here, as you only need to collectn
piles and the last third are the smallest ones taken by Bob. - Use a step of
-2
to simulate the turns, meaning you take every other pile from the end of the sortedpiles
.
Following this slicing, we would pick the piles at indices
-2
and-4
which correspond to the values[7, 4]
in the original sortedpiles
. - Start from the second-to-last element to avoid the largest pile, which Alice takes. This gives us a starting point of
-
Summation: Summing the slice
[7, 4]
gives us11
. This is the maximum number of coins you can gather following this strategy.
Therefore, by applying the greedy algorithm, we were able to maximize your share of the coins to 11
. This example validates the approach described and shows how sorting, slicing, and summing in a strategic manner results in an optimal solution for you in this coin pile game.
Solution Implementation
1class Solution:
2 def maxCoins(self, piles):
3 # Sort the piles in ascending order.
4 piles.sort()
5
6 # Initialize the total coins collected.
7 total_coins = 0
8
9 # We start taking coins from the second largest pile (hence -2 index)
10 # and continue with every second pile from the end until we reach
11 # the point which is just beyond one third of the piles count from the end.
12 # This allows us to simulate the process of taking piles from the end,
13 # skipping the smallest one each time and ignoring the smallest third.
14 for i in range(len(piles) // 3, len(piles), 2):
15 total_coins += piles[i]
16
17 # Return the total coins collected.
18 return total_coins
19
1import java.util.Arrays; // Import necessary class for sorting
2
3class Solution {
4
5 /**
6 * Calculate the maximum number of coins you can get.
7 * @param piles Array of piles where each pile has a certain number of coins.
8 * @return The maximum coins that can be taken.
9 */
10 public int maxCoins(int[] piles) {
11 // Sort the array to arrange the piles in ascending order
12 Arrays.sort(piles);
13
14 // Initialize answer to 0, this will hold the sum of coins picked
15 int maxCoins = 0;
16
17 // Start from the second largest pile and move backwards in steps of 2
18 // This approach ensures that we take the second largest piles leaving the smallest ones
19 for (int i = piles.length - 2; i >= piles.length / 3; i -= 2) {
20 // Add the number of coins from the current selected pile to the answer
21 maxCoins += piles[i];
22 }
23
24 // Return the calculated maximum number of coins
25 return maxCoins;
26 }
27}
28
1#include <vector>
2#include <algorithm> // Include algorithm for std::sort
3
4class Solution {
5public:
6 // Function to maximize the number of coins you can get.
7 int maxCoins(vector<int>& piles) {
8 // Sort the piles in ascending order.
9 std::sort(piles.begin(), piles.end());
10
11 int totalCoins = 0; // This will store the total number of coins you can get.
12
13 // Start from the second-largest pile and move two steps backward
14 // each time to get to the next pile you can take.
15 for (int i = piles.size() - 2; i >= piles.size() / 3; i -= 2) {
16 totalCoins += piles[i]; // Add the coins from the current pile to your total.
17 }
18
19 // Return the total number of coins.
20 return totalCoins;
21 }
22};
23
1function maxCoins(piles: number[]): number {
2 // Sort the array in ascending order.
3 piles.sort((a, b) => a - b);
4
5 // Get the total number of piles.
6 const totalPiles = piles.length;
7
8 // Initialize the maximum number of coins.
9 let maxCoins = 0;
10
11 // Calculate the number of times we can pick piles according to the rules.
12 const timesToPick = Math.floor(totalPiles / 3);
13
14 // Iterate to pick the second-largest pile from each triplet from the end.
15 for (let i = 1; i <= timesToPick; i++) {
16 // The index for the second-largest pile in each triplet
17 const index = totalPiles - 2 * i;
18
19 // Accumulate the number of coins from the chosen piles.
20 maxCoins += piles[index];
21 }
22
23 // Return the maximum number of coins we can collect.
24 return maxCoins;
25}
26
Time and Space Complexity
Time Complexity
The time complexity of the given code is determined primarily by the sort operation and the slicing to sum up the required coins.
-
Sorting the
piles
list is the most computationally heavy operation. The sort function in Python typically uses Timsort, which has a time complexity of O(n log n), wheren
is the number of elements in the list to sort. -
The slicing and summing operations occur after sorting. Slicing in Python is O(k), where
k
is the number of elements in the slice. However, in this case, the code is slicing from the second-to-last element down to a third of the list's length, creating a subsequence. The sum function operates over this subsequence. Its complexity is O(m), wherem
is the length of the subsequence.
The value of m
is approximately (2/3)n/2
elements because we start at the second to last element and take every second element till we reach the first third of the array. Thus, the slice and sum operation would have a complexity of O(n).
Combining both the sorting and the summation complexities, the time complexity of the code is O(n log n) + O(n), which simplifies to O(n log n) because the sorting complexity dominates the overall time complexity.
Space Complexity
The space complexity of the code consists of the additional space required for the sorted array and space for the variables used in summing operation:
-
The
.sort()
method sorts the list in place and therefore does not require additional space, so this contributes O(1) space complexity. -
Slicing does not create a new list; it creates a view on the existing list, which also is O(1) space complexity since it's not duplicating the entire list.
-
Variable space for the sum operation is negligible and constant, so adds O(1).
Considering all the extra space required, the overall space complexity of the function is O(1), since no additional space proportional to the input size is created.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!