Maximum Number of Coins You Can Get - Video Solutions

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).