Problem Description

You are playing a coin collection game with two other people - Alice and Bob. There are 3n piles of coins with different amounts in each pile.

The game works as follows:

• In each round, you select any 3 piles of coins from the remaining piles
• Alice always takes the pile with the most coins from these 3 piles
• You take the pile with the second-most coins
• Bob gets the pile with the least coins
• This process repeats until all piles are taken

Given an array piles where piles[i] represents the number of coins in the i-th pile, your goal is to find the maximum number of coins you can collect.

For example, if there are 6 piles with coins [2, 4, 1, 2, 7, 8], one optimal strategy would be:

• Round 1: Choose piles with [8, 7, 2] - Alice gets 8, you get 7, Bob gets 2
• Round 2: Choose piles with [4, 2, 1] - Alice gets 4, you get 2, Bob gets 1
• Total coins you get: 7 + 2 = 9

The key insight is that since Alice always takes the maximum and Bob always gets the minimum from each selection of 3 piles, you need to strategically choose which 3 piles to select in each round to maximize your total coins as the person who gets the middle value.

Intuition

Since we always get the second-largest pile from any group of 3 piles we choose, and Alice always gets the largest, we need to think about how to maximize our gains while minimizing what we "waste" on Bob.

The key realization is that Bob is forced to take the smallest pile from each group of 3. So if we want to maximize our coins, we should "sacrifice" the smallest piles to Bob. This way, we can pair ourselves with larger piles.

Think about it this way: if we sort all piles in ascending order, we can give Bob the smallest n piles (since there are 3n piles total and we play n rounds). This leaves us with the largest 2n piles to split between Alice and ourselves.

From these remaining 2n piles, Alice will take n piles and we'll take n piles. Since Alice always gets the maximum from each group, the best strategy is to pair ourselves as closely as possible with Alice's picks.

For example, with sorted piles [1, 2, 3, 4, 5, 6, 7, 8, 9]:

• We give Bob: [1, 2, 3] (the smallest third)
• Remaining for Alice and us: [4, 5, 6, 7, 8, 9]
• We pair them as: (9, 8), (7, 6), (5, 4)
• Alice gets: [9, 7, 5]
• We get: [8, 6, 4]

This greedy approach ensures we get the maximum possible coins by taking every second element from the larger 2n piles, starting from the second-largest pile.

Learn more about Greedy, Math and Sorting patterns.

Solution Approach

The implementation follows a greedy strategy with sorting:

1. Sort the array: First, we sort the piles array in ascending order. This allows us to easily identify which piles should go to Bob (the smallest ones) and which should be divided between Alice and us (the largest ones).

2. Discard the smallest n piles: Since there are 3n piles total and we play n rounds, Bob will get n piles in total. We give him the smallest n piles by ignoring the first third of the sorted array. This is done with piles[len(piles) // 3:], which takes all elements starting from index n (where n = len(piles) // 3).

3. Take every second element from the remaining piles: From the remaining 2n largest piles, we need to simulate the pairing where Alice takes the maximum and we take the second maximum from each pair. When these piles are already sorted, this means:

   • From the last two piles, Alice gets the largest, we get the second-largest
   • From the next two piles, Alice gets the larger, we get the smaller
   • And so on...

   This pattern is achieved by taking every second element starting from index 0 of the remaining array, which is done with [::2] slice notation.

4. Sum our coins: Finally, we sum all the piles we've collected using sum().

For example, with piles = [1, 2, 3, 4, 5, 6, 7, 8, 9]:

• After sorting (already sorted): [1, 2, 3, 4, 5, 6, 7, 8, 9]
• After removing first third: [4, 5, 6, 7, 8, 9]
• Taking every second element: [4, 6, 8]
• Sum: 4 + 6 + 8 = 18

The time complexity is O(n log n) due to sorting, and the space complexity is O(1) if we don't count the space used by the sorting algorithm.

Example Walkthrough

Let's walk through a small example with piles = [9, 8, 7, 6, 5, 1] (6 piles total, so we'll play 2 rounds).

Step 1: Sort the array After sorting: [1, 5, 6, 7, 8, 9]

Step 2: Identify which piles go to Bob Since we have 6 piles (3n where n=2), Bob will get 2 piles total (the smallest ones). We discard the first n=2 piles: [1, 5] go to Bob. Remaining piles for Alice and us: [6, 7, 8, 9]

Step 3: Pair up the remaining piles optimally From the remaining 4 piles, we need to form 2 groups of (Alice, You):

• Looking at [6, 7, 8, 9] in reverse pairs:
  • Pair 1: (9, 8) - Alice gets 9, you get 8
  • Pair 2: (7, 6) - Alice gets 7, you get 6

Step 4: Extract our piles Taking every second element from [6, 7, 8, 9] starting at index 0:

• Index 0: 6 (take)
• Index 1: 7 (skip)
• Index 2: 8 (take)
• Index 3: 9 (skip)
• Our piles: [6, 8]

Step 5: Calculate the sum Total coins for us: 6 + 8 = 14

Verification with actual game rounds:

• Round 1: Choose piles [1, 8, 9] → Alice: 9, You: 8, Bob: 1
• Round 2: Choose piles [5, 6, 7] → Alice: 7, You: 6, Bob: 5
• Your total: 8 + 6 = 14 ✓

The algorithm correctly maximizes our coins by ensuring Bob gets the smallest piles overall, allowing us to pair with larger values.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the number of piles of coins. This is dominated by the piles.sort() operation, which uses a comparison-based sorting algorithm (typically Timsort in Python) that has O(n × log n) time complexity. The subsequent slicing and summation operations take O(n) time, but this is absorbed by the larger sorting complexity.

The space complexity is O(log n). While the slicing operation piles[len(piles) // 3:][::2] creates a new list that takes O(n) space, the dominant space consideration for complexity analysis is the auxiliary space used by the sorting algorithm. Python's Timsort uses O(log n) space for its recursive call stack during the sorting process. The temporary space for the slice is typically not counted in the space complexity analysis when considering the algorithm's auxiliary space requirements.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Selection Strategy

The Problem: Many people initially think they need to simulate the actual game rounds by selecting specific triplets of piles. They might try to implement complex logic to choose which 3 piles to select in each round, attempting to maximize their coins while considering what Alice and Bob will get.

Why It Happens: The problem statement describes the game procedurally (selecting 3 piles each round), which leads to overthinking the implementation as a simulation.

The Solution: Recognize that you have complete control over which triplets are formed. The optimal strategy is straightforward: give Bob all the smallest piles, then pair up the remaining piles so you get the second-largest from each pair. This translates to the sorted array approach without needing to explicitly form triplets.

Pitfall 2: Incorrect Index Calculation After Sorting

The Problem: After sorting, some might incorrectly calculate which elements to take. Common mistakes include:

• Taking elements from index 0 with step 2 from the entire sorted array: piles[::2]
• Taking the wrong slice after removing Bob's piles: piles[len(piles)//3::2] vs piles[len(piles)//3:][::2]

Why It Happens: Confusion about slice notation and how to properly skip Bob's piles before selecting every second element.

The Solution: Break it down into two clear steps:

1. First, remove Bob's n smallest piles: remaining = piles[len(piles)//3:]
2. Then, take every second element from the remaining: remaining[::2]

Or combine them carefully: piles[len(piles)//3::2] (starting from index n with step 2).

Pitfall 3: Off-by-One Errors in Alternative Approaches

The Problem: When implementing an alternative approach that iterates through pairs from the end of the sorted array, it's easy to make off-by-one errors:

# Incorrect - might access wrong indices
result = 0
for i in range(len(piles)-2, len(piles)//3, -2):
    result += piles[i]

Why It Happens: Working backwards through arrays with specific step sizes requires careful calculation of start and end indices.

The Solution: Use the cleaner slice-based approach, or if iterating, carefully verify the loop bounds:

# Correct iteration approach
result = 0
n = len(piles) // 3
for i in range(n):
    # Take the second-largest from each pair at the end
    result += piles[len(piles) - 2 - 2*i]

Pitfall 4: Not Considering Edge Cases

The Problem: Failing to consider minimum constraints like when piles has exactly 3 elements (n=1), leading to potential index errors or incorrect logic.

Why It Happens: The algorithm seems straightforward for larger inputs, making it easy to overlook boundary cases.

The Solution: The given approach naturally handles all valid cases since:

• For n=1 (3 piles): We skip 1 pile for Bob, take element at index 1 (the middle value)
• The slice notation [start::2] works correctly even for small arrays
• The problem guarantees len(piles) % 3 == 0 and len(piles) >= 3