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:

  1. Alice will always take the pile with the largest number of coins.
  2. You will take the next largest pile.
  3. 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:

  1. We start from the second element from the end, as this would have been the largest pile if we picked any three piles.
  2. 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.
  3. We stop picking after we have selected n piles for ourselves, which happens after n iterations as there are 3n 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.

Learn more about Greedy, Math and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

How many ways can you arrange the three letters A, B and C?

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:

  1. 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.

  2. 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.
  3. 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).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Example 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:

  1. Sorting the Piles: First, sort piles to get [1, 2, 2, 4, 7, 8].

  2. 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 is 7.
    • End at len(piles) // 3 - 1 which is 1 here, as you only need to collect n 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 sorted piles.

    Following this slicing, we would pick the piles at indices -2 and -4 which correspond to the values [7, 4] in the original sorted piles.

  3. Summation: Summing the slice [7, 4] gives us 11. 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.

Not Sure What to Study? Take the 2-min Quiz:

Which of the following array represent a max heap?

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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
Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

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.

  1. 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), where n is the number of elements in the list to sort.

  2. 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), where m 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:

  1. The .sort() method sorts the list in place and therefore does not require additional space, so this contributes O(1) space complexity.

  2. 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.

  3. 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.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫