Maximum number of coins you can get

Array Math Greedy Sorting Game Theory

84.7% acceptance

Feb 25, 2026

1974

224

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 pile with the second maximum number of coins. Your friend Bob will pick the pile with the minimum number of coins. 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 you can have.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_coins(mut piles: Vec<i32>) -> i32 {
    piles.sort();
    let n = piles.len();
    // Take every other element from n/3 to n-2 (inclusive)
    // These are the second-largest in each optimal group
    (0..n / 3).map(|i| piles[n - 2 - 2 * i]).sum()
  }
}