Maximum Number of Coins You Can Get solution and explanation
9 more videos on this problem
maximum number of coins you can get | leetcode 1561 | array mediumNaresh Gupta · 4:15 · 5K views
Maximum Number of Coins You Can Get | Greedy | 2 Approaches | Leetcode - 1561codestorywithMIK · 22:18 · 4K views
LeetCode 1561. Maximum Number of Coins You Can Get - Interview Prep Ep 92Fisher Coder · 9:27 · 2K views
1561. Maximum Number of Coins You Can Get | Easy | GreedyAryan Mittal · 6:38 · 2K views
1561. Maximum Number of Coins You Can GetChhavi Bansal · 8:59 · 834 views
✅ Maximum Number of Coins You Can Get - Interview Solution Using Frequency -1561 LeetCode -ExplainedLeet Logics · 7:57 · 799 views
1561. Maximum Number of Coins You Can Get (Leetcode Medium)Programming Live with Larry · 3:39 · 451 views
Daily Leetcode #1333: Nov 24, 2023 - 1561. Maximum Number of Coins You Can GetProgramming Live with Larry · 7:43 · 444 views
Leetcode 1561: Maximum Number of Coins You Can GetAlgorithms Casts · 5:50 · 372 views
Solving LeetCode 1561 Maximum Number of Coins You Can Get | Greedy ProblemCode Harmony · 8:25 · 186 views
The problem
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
3piles 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 <= 105piles.length % 3 == 01 <= 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.
def maxCoins(piles):
piles.sort()
result = 0
n = len(piles) // 3
for i in range(n, len(piles), 2):
result += piles[i]
return result
piles = [2, 4, 1, 2, 7, 8]
print(maxCoins(piles))import java.util.Arrays;
public class MaxCoins {
public static int maxCoins(int[] piles) {
Arrays.sort(piles);
int result = 0;
int n = piles.length / 3;
for (int i = n; i < piles.length; i += 2) {
result += piles[i];
}
return result;
}
public static void main(String[] args) {
int[] piles = {2, 4, 1, 2, 7, 8};
System.out.println(maxCoins(piles));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxCoins(std::vector<int>& piles) {
std::sort(piles.begin(), piles.end(), std::greater<int>());
int result = 0;
for (int i = 1, j = piles.size() - 1; i < j; i += 2, --j) {
result += piles[i];
}
return result;
}
int main() {
std::vector<int> piles = {2, 4, 1, 2, 7, 8};
std::cout << maxCoins(piles) << std::endl;
return 0;
}function maxCoins(piles) {
piles.sort((a, b) => a - b);
let result = 0;
let n = piles.length / 3;
for (let i = n; i < piles.length; i += 2) {
result += piles[i];
}
return result;
}
const piles = [2, 4, 1, 2, 7, 8];
console.log(maxCoins(piles));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int maxCoins(int* piles, int pilesSize) {
qsort(piles, pilesSize, sizeof(int), compare);
int result = 0;
for (int i = 1, j = pilesSize - 1; i < j; i += 2, j--) {
result += piles[i];
}
return result;
}
int main() {
int piles[] = {2, 4, 1, 2, 7, 8};
int size = sizeof(piles) / sizeof(piles[0]);
printf("%d\n", maxCoins(piles, size));
return 0;
}using System;
using System.Linq;
public class Solution {
public int MaxCoins(int[] piles) {
Array.Sort(piles);
int result = 0;
int n = piles.Length / 3;
for (int i = n; i < piles.Length; i += 2) {
result += piles[i];
}
return result;
}
public static void Main() {
int[] piles = new int[] {2, 4, 1, 2, 7, 8};
Solution sol = new Solution();
Console.WriteLine(sol.MaxCoins(piles));
}
}We sort the piles array, then iterate through the elements starting from the index n, taking every second element after to sum up to our result.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting modifies the list in place.
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.
def maxCoins(piles):
piles.sort()
result = 0
index = len(piles) - 2
for _ in range(len(piles) // 3):
result += piles[index]
index -= 2
return result
piles = [2, 4, 1, 2, 7, 8]
print(maxCoins(piles))import java.util.Arrays;
public class MaxCoins {
public static int maxCoins(int[] piles) {
Arrays.sort(piles);
int result = 0;
int index = piles.length - 2;
for (int i = 0; i < piles.length / 3; i++) {
result += piles[index];
index -= 2;
}
return result;
}
public static void main(String[] args) {
int[] piles = {2, 4, 1, 2, 7, 8};
System.out.println(maxCoins(piles));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxCoins(std::vector<int>& piles) {
std::sort(piles.begin(), piles.end(), std::greater<int>());
int result = 0;
int index = 0;
for (int i = 0; i < piles.size() / 3; ++i) {
index += 2;
result += piles[index];
}
return result;
}
int main() {
std::vector<int> piles = {2, 4, 1, 2, 7, 8};
std::cout << maxCoins(piles) << std::endl;
return 0;
}function maxCoins(piles) {
piles.sort((a, b) => a - b);
let result = 0;
for (let i = piles.length - 2; i >= piles.length / 3; i -= 2) {
result += piles[i];
}
return result;
}
const piles = [2, 4, 1, 2, 7, 8];
console.log(maxCoins(piles));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int maxCoins(int* piles, int pilesSize) {
qsort(piles, pilesSize, sizeof(int), compare);
int result = 0;
int index = 0;
for (int i = 0; i < pilesSize / 3; ++i) {
index += 2;
result += piles[index];
}
return result;
}
int main() {
int piles[] = {2, 4, 1, 2, 7, 8};
int size = sizeof(piles) / sizeof(piles[0]);
printf("%d\n", maxCoins(piles, size));
return 0;
}using System;
using System.Linq;
public class Solution {
public int MaxCoins(int[] piles) {
Array.Sort(piles);
int result = 0;
int index = piles.Length - 2;
for (int i = 0; i < piles.Length / 3; i++) {
result += piles[index];
index -= 2;
}
return result;
}
public static void Main() {
int[] piles = new int[] {2, 4, 1, 2, 7, 8};
Solution sol = new Solution();
Console.WriteLine(sol.MaxCoins(piles));
}
}With an index strategy, we sort and choose the second max using a manipulated index, consistently reducing, focusing on sections Bob's smaller pile omits.
Time Complexity: O(n log n) because of sorting first.
Space Complexity: O(1) since in-place operations after sorting.
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.
function maxCoins(piles: number[]): number {
piles.sort((a, b) => a - b);
let ans = 0;
for (let i = piles.length / 3; i < piles.length; i += 2) {
ans += piles[i];
}
return ans;
}func maxCoins(piles []int) (ans int) {
sort.Ints(piles)
for i := len(piles) / 3; i < len(piles); i += 2 {
ans += piles[i]
}
return
}impl Solution {
pub fn max_coins(mut piles: Vec<i32>) -> i32 {
piles.sort();
let mut ans = 0;
for i in (piles.len() / 3..piles.len()).step_by(2) {
ans += piles[i];
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort and Select Strategy | Time Complexity: O(n log n) due to sorting. |
| Maximizing Through Index Analysis | Time Complexity: O(n log n) because of sorting first. |
| Greedy + Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Select Strategy | O(n log n) | O(1) or O(n) | General solution; easiest way to implement greedy selection after ordering piles |
| Maximizing Through Index Analysis | O(n log n) | O(1) | When you want to reason about exact indices you receive instead of simulating turns |
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.