Maximum Number of Coins You Can Get - Practice Coding Problems

Maximum Number of Coins You Can Get - Problem

Array Math Greedy Sorting Game Theory Medium

There are 3n piles of coins of varying size. You and your friends Alice and Bob will take piles of coins following this process:

In each step, you choose any 3 piles of coins (not necessarily consecutive)
Alice picks the pile with the maximum number of coins
You pick the pile with the next maximum number of coins
Bob picks the remaining pile
Repeat until no piles remain

Given an array piles where piles[i] is the number of coins in the i^th pile, return the maximum number of coins you can collect.

Input & Output

Example 1 — Basic Game

$ Input: piles = [2,4,1,2,7,8]

› Output: 9

💡 Note: Sort: [8,7,4,2,2,1]. Take positions 2,3: piles[2]=4, piles[3]=2. Total: 4+2=6. Wait, let me recalculate: n=2, take indices 2 to 3, which gives 4+2=6. But optimal is: Alice gets 8,7 and you get 4,2, Bob gets 2,1. Actually, you get 7+2=9.

Example 2 — Larger Array

$ Input: piles = [9,8,7,6,5,1]

› Output: 13

💡 Note: Sort: [9,8,7,6,5,1]. n=2, take indices 2,3: piles[2]=7, piles[3]=6. Total: 7+6=13

Example 3 — Equal Values

$ Input: piles = [1,1,1,1,1,1]

› Output: 2

💡 Note: All piles equal, sort doesn't change order. n=2, take indices 2,3: 1+1=2

Constraints

3 ≤ piles.length ≤ 10⁵
piles.length % 3 == 0
1 ≤ piles[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of pile sizes: [9,8,7,6,5,1]

Strategy

Sort piles and use greedy selection

Output

Maximum coins you can collect: 13

Key Takeaway

🎯 Key Insight: Sort the piles and take strategic middle positions to maximize your share

Asked in

f Facebook 15 G Google 12 a Amazon 8

The key insight is to sort the piles and use a greedy strategy. After sorting in descending order, take every element from position n to 2n-1. This ensures Alice gets the largest piles, you get the next best, and Bob gets the smallest. Best approach is greedy sorting. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Strategy (Sort First)	O(n log n)	O(1)	Sort piles and use greedy strategy to maximize your coins
Try All Combinations	O((3n)!)	O(n)	Generate all possible ways to group piles into triplets and find maximum coins

Greedy Strategy (Sort First) — Algorithm Steps

Sort all piles in descending order
Take every second element from position n to 2n-1
This ensures Alice takes the largest, you take second largest, Bob gets smallest

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Descending

Arrange piles from largest to smallest

Strategic Selection

Take positions n through 2n-1 (every other from middle section)

Optimal Result

This guarantees maximum coins for you

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int solution(int* piles, int pilesSize) {
    qsort(piles, pilesSize, sizeof(int), compare);
    int n = pilesSize / 3;
    int result = 0;
    
    // Take every second element from position n to 2n-1
    for (int i = n; i < 2 * n; i++) {
        result += piles[i];
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int piles[1000];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            piles[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(piles, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting dominates the time complexity

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Strategy (Sort First) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler