Skip to main content
Talentd

Maximum Number of Coins You Can Get - Solution & Explanation

MediumArrayMathGreedySorting16 min readAsked at: Amazon
Practice this problem

Problem Statement

There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

  • In each step, you will choose any 3 piles of coins (not necessarily consecutive).
  • Of your choice, Alice will pick the pile with the maximum number of coins.
  • You will pick the next pile with the maximum number of coins.
  • Your friend Bob will pick the last pile.
  • Repeat until there are no more piles of coins.

Given an array of integers piles where piles[i] is the number of coins in the ith pile.

Return the maximum number of coins that you can have.

 

Example 1:

Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.

Example 2:

Input: piles = [2,4,5]
Output: 4

Example 3:

Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18

 

Constraints:

  • 3 <= piles.length <= 105
  • piles.length % 3 == 0
  • 1 <= piles[i] <= 104

Approach Overview

Problem Overview: You are given 3n piles of coins. In every round, three piles are chosen: Alice takes the largest, you take the second largest, and Bob takes the smallest. The goal is to maximize the total number of coins you collect after all piles are used.

Approach 1: Sort and Select Strategy (Greedy with Sorting) (Time: O(n log n), Space: O(1) or O(n) depending on sort)

This problem becomes straightforward once the piles are sorted. After sorting the array in ascending order, the largest pile in each group goes to Alice and the smallest to Bob. You always take the second largest. Instead of simulating three picks every round, iterate from the second-largest position and skip elements strategically. Specifically, start from index n in the sorted array and keep jumping two steps toward the end while summing values. Sorting guarantees that the greedy choice (taking the second largest available pile) produces the maximum total.

The key insight: Bob always removes the smallest pile, which doesn't affect the large values you want. Alice always removes the largest. That leaves you consistently taking the next best option. Sorting simplifies the decision-making process and converts the game into predictable index traversal. This technique commonly appears in greedy problems involving optimal selection after ordering elements.

Approach 2: Maximizing Through Index Analysis (Greedy Observation) (Time: O(n log n), Space: O(1))

Instead of thinking about players picking piles, analyze the pattern of indices after sorting. With 3n piles, exactly n rounds occur. Alice always consumes the largest pile of each triplet, Bob consumes the smallest, and you receive the middle value. After sorting, the piles you obtain correspond to positions starting from len(piles) - 2 and moving left by two steps each round while skipping Bob's piles at the beginning.

Practically, maintain two pointers: one pointing to the largest remaining pile and another implicitly tracking Bob's removals. Each round skips the largest (Alice), adds the next (your pile), and moves past Bob's smallest. This index-based reasoning avoids explicitly grouping triplets and makes the greedy logic clear. The algorithm still depends on sorting, but the index math explains why the greedy strategy is optimal.

The method relies on predictable ordering rather than simulation. Once sorted, the game outcome is fixed. This approach highlights how analyzing index positions in an array can simplify multi-player selection problems.

Recommended for interviews: The greedy sorting approach with index traversal is what interviewers expect. It shows you recognize that the game rules reduce to a deterministic pattern after sorting. Explaining why you always take the second-largest pile demonstrates strong greedy reasoning. A brute-force simulation would work but adds unnecessary complexity, while the sorted greedy approach solves the problem cleanly in O(n log n).

Approach 1: Sort and Select Strategy

This approach involves sorting the piles of coins first. After sorting, one can consistently select the second largest pile from each group of three piles (Alice's bigger pile, your pile, and Bob's smaller pile) to maximize your coins.

By sorting the piles in descending order, the strategy becomes easier. Alice will always pick the first pile, you will always pick the second pile, and Bob will take the third.

Firstly, we sort the array in descending order using the C standard library's `qsort` function. Then, starting from the second element of the sorted array, we add every second element to our result (since these represent the second largest coin piles in the sorted groups of three).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.

Try this approach in the editor →

Approach 2: Maximizing Through Index Analysis

Another approach, although less direct than sorting, involves analyzing the positions of piles through controlled index manipulation to ensure Alice always takes the maximum pile, you take the second, and Bob takes the least of the three for every set of operations.

Sort the array in descending order. You'll manipulate the index to "skip" the maximum pile (chosen by Alice), select the second, and continue, excluding the least of the three per group chosen by Bob.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) because of sorting the array.
Space Complexity: O(1) as index manipulation happens in place.

Try this approach in the editor →

Approach 3: Greedy + Sorting

To maximize the number of coins we get, we can greedily let Bob take the smallest n piles of coins. Each time, we let Alice take the largest pile of coins, then we take the second largest pile of coins, and so on, until there are no more coins to take.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of piles of coins.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sort and Select Strategy

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.

Maximizing Through Index Analysis

Time Complexity: O(n log n) because of sorting the array.
Space Complexity: O(1) as index manipulation happens in place.

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and Select StrategyO(n log n)O(1) or O(n)General solution; easiest way to implement greedy selection after ordering piles
Maximizing Through Index AnalysisO(n log n)O(1)When you want to reason about exact indices you receive instead of simulating turns

Video Solution

maximum number of coins you can get | leetcode 1561 | array medium • Naresh Gupta • 5,832 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Number of Coins You Can Get easy or hard?
Maximum Number of Coins You Can Get is categorized as Medium difficulty. The implementation is simple once you recognize the greedy pattern, but the key challenge is realizing that sorting reveals a fixed selection order where you always take the second-largest pile.
Maximum Number of Coins You Can Get Python/Java solution
In Python or Java, the typical solution sorts the array and iterates from the second-largest element toward the middle while skipping elements appropriately. Each step adds the pile you receive to the result. Implementations are concise and usually under 10–15 lines after sorting.
How to solve Maximum Number of Coins You Can Get in O(n)?
An O(n) solution is not possible for the general case because the greedy decision depends on ordering the piles. Sorting is required to determine which piles are largest in each round. After sorting, you can collect the second-largest pile in each triplet using simple index traversal.
What is the best approach for Maximum Number of Coins You Can Get?
The optimal approach is a greedy strategy combined with sorting. Sort the piles in ascending order and repeatedly take the second largest pile from each group of three. Alice always takes the largest and Bob the smallest, so your piles appear at predictable indices after sorting. This solution runs in O(n log n) time due to sorting.
Is Maximum Number of Coins You Can Get asked at Google/Amazon/Meta?
Greedy and sorting problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests your ability to recognize patterns after sorting and reason about deterministic outcomes in a multi-player selection game.
What data structure is used in Maximum Number of Coins You Can Get?
The primary data structure is an array of integers representing coin piles. The algorithm relies on sorting the array and then using index traversal or pointer movement to select the optimal piles using a greedy strategy.
What is the time complexity of Maximum Number of Coins You Can Get?
The dominant operation is sorting the piles, which takes O(n log n) time where n is the number of piles. After sorting, iterating through the relevant indices to collect your coins takes O(n). The overall space complexity is O(1) or O(n) depending on the sorting implementation.

Ready to solve this problem?

Practice Maximum Number of Coins You Can Get with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays