LeetCode Problem 1561

Difficulty: 🟡 Medium
Topics: Array, Math, Greedy, Sorting, Game Theory

Solution

LeetCode 1561 - Maximum Number of Coins You Can Get

Problem Understanding

The problem gives us an array called piles, where each element represents the number of coins in a pile. The length of the array is always divisible by 3, meaning there are exactly 3n piles for some integer n.

In every round, three piles are selected. Among those three piles:

• Alice always takes the largest pile.
• You take the second largest pile.
• Bob takes the smallest pile.

This process continues until all piles are used.

The goal is to maximize the total number of coins that you collect.

The key detail is that we are allowed to choose any three piles in each step. The piles do not need to be adjacent, and we can arrange the grouping strategically. Since Alice always takes the largest pile in the chosen triplet, we cannot keep the largest piles for ourselves directly. However, we can still structure the selections so that we consistently receive large piles as the second largest choice.

The constraints are important:

• piles.length can be as large as 10^5
• Each pile can contain up to 10^4 coins

Because the input size is large, exponential or quadratic simulation approaches are not practical. We need an efficient algorithm, ideally dominated only by sorting.

Several edge cases are worth noticing upfront:

• The smallest valid input has only 3 piles.
• Many piles may contain identical values.
• The array may already be sorted or reverse sorted.
• Extremely large values near the constraint limit should still work efficiently.
• A naive greedy grouping strategy can fail if it does not account for Alice always taking the largest pile.

Approaches

Brute Force Approach

A brute force solution would try every possible way to partition the piles into groups of three and then simulate the selections.

For every grouping:

1. Alice takes the maximum pile.
2. You take the second maximum.
3. Bob takes the minimum.

We would compute your total and keep the maximum across all possible arrangements.

This approach is correct because it explores every possible configuration, guaranteeing that the optimal arrangement is found.

However, it is computationally impossible for the given constraints. The number of ways to partition 3n items into triplets grows extremely quickly. Even for relatively small inputs, the number of combinations becomes enormous.

Therefore, brute force is only useful conceptually, not practically.

Optimal Greedy Approach

The key insight comes from understanding how to maximize the piles that you receive.

After sorting the piles in ascending order:

• Alice will always take the largest remaining pile.
• Bob should receive the smallest remaining pile whenever possible.
• You should receive the next largest pile after Alice's choice.

To achieve this, we pair:

• The largest pile for Alice
• The second largest pile for ourselves
• The smallest pile for Bob

This strategy wastes the smallest piles on Bob while preserving large piles for ourselves.

After sorting, we can repeatedly:

• Skip the largest pile, Alice takes it
• Take the next largest pile for ourselves
• Ignore one smallest pile for Bob

This produces the maximum possible total.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries every possible grouping of triplets
Optimal	O(n log n)	O(1) or O(log n) depending on sort	Sorts the array and greedily selects second largest piles

Algorithm Walkthrough

1. Sort the array in ascending order.

Sorting allows us to reason about the smallest and largest remaining piles efficiently. Once sorted, the largest piles are at the end of the array. 2. Observe the optimal assignment pattern.

In every group of three:

• Alice should take the current largest pile.
• You should take the next largest pile.
• Bob should take the smallest remaining pile.

This minimizes the waste caused by Bob while maximizing your gain. 3. Initialize pointers.

Let:

• left = 0, pointing to the smallest remaining pile
• right = len(piles) - 2, pointing to the second largest remaining pile

We start at len(piles) - 2 because the largest pile at the end is effectively reserved for Alice. 4. Repeat n times.

Since there are 3n piles, there will be exactly n rounds.

In each round:

• Add piles[right] to your answer
• Move right two positions left
• Move left one position right

Moving right by two skips:

• One pile for Alice
• One pile for yourself

Moving left by one removes the smallest pile for Bob. 5. Return the accumulated answer.

Why it works

The greedy strategy works because Bob always receives the smallest pile in each triplet, so the smallest values contribute nothing useful to your score. Therefore, the optimal strategy is to sacrifice the smallest piles to Bob while reserving the largest possible second-largest values for yourself.

After sorting, every optimal grouping can be rearranged into this pattern without reducing your total. Thus, greedily selecting every second pile from the right side guarantees the maximum achievable sum.

Python Solution

from typing import List

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles.sort()

        total = 0
        left = 0
        right = len(piles) - 2
        rounds = len(piles) // 3

        for _ in range(rounds):
            total += piles[right]

            left += 1
            right -= 2

        return total

The implementation begins by sorting the array so that the smallest and largest piles are easy to access.

The variable total stores the number of coins you collect. The right pointer starts at the second largest element because the largest element is assumed to go to Alice in each round. The left pointer tracks the smallest remaining pile that will go to Bob.

The loop runs exactly n times, where n = len(piles) // 3. During each iteration:

• piles[right] is added to your total.
• right -= 2 skips both Alice's pile and your chosen pile.
• left += 1 removes Bob's smallest pile.

At the end, total contains the maximum number of coins you can obtain.

Go Solution

package main

import (
	"sort"
)

func maxCoins(piles []int) int {
	sort.Ints(piles)

	total := 0
	right := len(piles) - 2
	rounds := len(piles) / 3

	for i := 0; i < rounds; i++ {
		total += piles[right]
		right -= 2
	}

	return total
}

The Go implementation follows the exact same greedy logic as the Python version.

The standard library function sort.Ints() sorts the slice in ascending order. Since Go slices are mutable references to arrays, sorting happens in place.

Unlike Python, Go does not require a separate left pointer because we never directly access the smallest elements. We only need to track the positions of the piles that we collect.

Integer overflow is not a concern because the maximum possible answer fits comfortably inside Go's int type under the given constraints.

Worked Examples

Example 1

Input:

piles = [2,4,1,2,7,8]

After sorting:

[1,2,2,4,7,8]

There are 6 / 3 = 2 rounds.

Round	Alice Takes	You Take	Bob Takes	Total
1	8	7	1	7
2	4	2	2	9

Final answer:

9

Example 2

Input:

piles = [2,4,5]

After sorting:

[2,4,5]

There is only one round.

Round	Alice Takes	You Take	Bob Takes	Total
1	5	4	2	4

Final answer:

4

Example 3

Input:

piles = [9,8,7,6,5,1,2,3,4]

After sorting:

[1,2,3,4,5,6,7,8,9]

There are 9 / 3 = 3 rounds.

Round	Alice Takes	You Take	Bob Takes	Total
1	9	8	1	8
2	7	6	2	14
3	5	4	3	18

Final answer:

18

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on the sorting implementation

The main cost comes from sorting the array. After sorting, the greedy traversal only requires a single linear pass through one-third of the elements.

The algorithm itself uses constant extra space beyond the sorting process. Some sorting implementations may use logarithmic recursion stack space internally.

Test Cases

from typing import List

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles.sort()

        total = 0
        right = len(piles) - 2

        for _ in range(len(piles) // 3):
            total += piles[right]
            right -= 2

        return total

solution = Solution()

assert solution.maxCoins([2, 4, 1, 2, 7, 8]) == 9  # example 1
assert solution.maxCoins([2, 4, 5]) == 4  # example 2
assert solution.maxCoins([9, 8, 7, 6, 5, 1, 2, 3, 4]) == 18  # example 3

assert solution.maxCoins([1, 1, 1]) == 1  # minimum valid input
assert solution.maxCoins([1, 2, 3]) == 2  # simple increasing order
assert solution.maxCoins([3, 2, 1]) == 2  # simple decreasing order

assert solution.maxCoins([2, 2, 2, 2, 2, 2]) == 4  # all equal values
assert solution.maxCoins([1, 100, 2, 99, 3, 98]) == 198  # alternating small and large
assert solution.maxCoins([10, 20, 30, 40, 50, 60]) == 80  # balanced increasing values

assert solution.maxCoins([10000] * 3000) == 10000 * 1000  # large identical values

Test	Why
[2,4,1,2,7,8]	Validates the primary example
[2,4,5]	Tests minimum number of rounds
[9,8,7,6,5,1,2,3,4]	Tests multiple greedy selections
[1,1,1]	Tests smallest valid input
[1,2,3]	Tests sorted ascending input
[3,2,1]	Tests sorted descending input
[2,2,2,2,2,2]	Tests duplicate values
[1,100,2,99,3,98]	Tests greedy correctness with large gaps
[10,20,30,40,50,60]	Tests standard increasing sequence
[10000] * 3000	Stress test with large values

Edge Cases

One important edge case is the smallest possible input size, where there are exactly three piles. In this scenario, there is only one round. A buggy implementation might incorrectly move pointers or assume multiple iterations exist. The current implementation handles this naturally because the loop runs exactly once.

Another important case occurs when all pile sizes are identical. Since every pile has the same value, there are many equally valid groupings. Some implementations accidentally rely on strict inequalities or special ordering assumptions. The sorting-based greedy approach works correctly because every second-largest pile still has the same value.

A third edge case involves arrays that are already sorted in descending order. If the implementation assumes ascending order without explicitly sorting, the logic fails completely. By always sorting the input first, the algorithm guarantees that the pointer strategy operates on a properly ordered sequence.

A final important case involves very large arrays near the maximum constraint size. Inefficient approaches that repeatedly remove elements or simulate triplets with expensive operations can become too slow. This implementation only sorts once and then performs a simple linear traversal, making it efficient even for the largest allowed inputs.