Problem Explanation:

You along with friends Alice and Bob play a game where you have to pick piles of coins. There are in total 3n piles available, each of different sizes. You pick piles in steps. In each step, any three piles can be chosen (not necessarily in order). Alice picks the pile which has the maximum number of coins, you pick the next biggest pile and Bob picks the last remaining pile. This continues till there are no more piles to choose. You have to maximize the number of coins you can get at the end of all the steps.

Given a list of integers where each integer denotes the number of coins in a pile, you need to determine the maximum number of coins you can get.

Approach:

The approach used in this problem is straightforward and simple. We first sort the piles in ascending order, and then accumulate the sum of every second number starting from n/3 (where n is the number of piles) index to the end of the array. These are the piles you end up picking and we aim to maximize the sum of ice.

We want to always leave the smallest piles to Bob, so we start accumulating the piles to pick from piles.length / 3 index. And we want to leave the biggest piles to Alice, so we increment the index by 2 to miss out the largest pile in each triplet.

Example:

Let's consider the example piles = [9,8,7,6,5,1,2,3,4]. After sorting the piles, we get [1,2,3,4,5,6,7,8,9]. We leave the first 3 smallest piles to Bob, and start picking from the 4th index. So we pick 5, 7 and 9 giving a maximum sum of 21.

Python Solution:

1
2python
3class Solution:
4    def maxCoins(self, piles: List[int]) -> int:
5        piles.sort()
6        n = len(piles)
7        coins = sum(piles[n//3::2]) #every second number starting from n/3
8        return coins

Java Solution:

1
2java
3class Solution {
4    public int maxCoins(int[] piles) {
5        int n = piles.length, res = 0, i = 0, maxCoins = n / 3;
6        Arrays.sort(piles);
7        for(i = maxCoins; maxCoins < n; i += 2, maxCoins++) {
8            res += piles[i];
9        }
10        return res;
11    }
12}

Javascript Solution:

1
2javascript
3var maxCoins = function(piles) {
4    piles.sort((a, b) => a - b);
5    let n = piles.length, res = 0;
6    n = n / 3;
7    for(let i = piles.length / 3; i < piles.length; i += 2) {
8        res += piles[i];
9    }
10    return res;
11};

C++ Solution:

1
2c++
3class Solution {
4public:
5    int maxCoins(vector<int>& piles) {
6        sort(piles.begin(), piles.end());
7        int res = 0;
8        for(int i = piles.size() / 3; i < piles.size(); i += 2)
9            res += piles[i];
10        return res;
11    }
12};

C# Solution:

1
2csharp
3public class Solution {
4    public int MaxCoins(int[] piles) {
5        Array.Sort(piles);
6        int res = 0;
7        for (int i = piles.Length / 3; i < piles.Length; i += 2) { 
8            res += piles[i];
9        }
10        return res;
11    }
12}

In all the solutions, we first sort the array of piles. We then start picking every second pile from piles.length / 3 index. These picked piles are accumulated to maximize the total number of coins you can get.Each of these solutions uses the same basic algorithm, with their syntax specific to the language used. Let's understand the algorithm step by step:

1. Sort Array: The first step is to sort the array in ascending or non-decreasing order. This step is done so that we can correctly distribute the piles among Alice, You, and Bob.

2. Initialize Variables: Initialize res (stores the result) and i (used for traversing the array). We also calculate the number of coins you can get by dividing the total number of coins (n) by 3.

3. Traverse Array: Start a loop from piles.length / 3 index (because we are leaving the smallest piles to Bob) and till the end of the piles array. Increment the index by 2 (because we are leaving the largest pile in each triplet to Alice).

4. Accumulate Coins: In each loop iteration, add the coins from the current pile to result (res). The piles[i] gives the number of coins in the current pile.

5. Return Result: After traversing all the piles, return the result.

The three solutions given in Python, Java, and Javascript, implement this algorithm accurately, specifically:

• The Python solution makes use of list comprehension to directly calculate the sum of coins by slicing the list starting from n // 3 index and considering every second number using the step argument in the list slice.

• In the Java solution, the Arrays.sort method is used for sorting the array, and a for loop is used to traverse the array and accumulate the result.

• The JavaScript solution also performs similar operations with the sort method used for sorting and a for loop used to traverse the array and accumulate the result.