Watch 10 video solutions for Maximum Score From Removing Stones, a medium level problem involving Math, Greedy, Heap (Priority Queue). This walkthrough by CS FOR ALL has 1,481 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are playing a solitaire game with three piles of stones of sizes a, b, and c respectively. Each turn you choose two different non-empty piles, take one stone from each, and add 1 point to your score. The game stops when there are fewer than two non-empty piles (meaning there are no more available moves).
Given three integers a, b, and c, return the maximum score you can get.
Example 1:
Input: a = 2, b = 4, c = 6 Output: 6 Explanation: The starting state is (2, 4, 6). One optimal set of moves is: - Take from 1st and 3rd piles, state is now (1, 4, 5) - Take from 1st and 3rd piles, state is now (0, 4, 4) - Take from 2nd and 3rd piles, state is now (0, 3, 3) - Take from 2nd and 3rd piles, state is now (0, 2, 2) - Take from 2nd and 3rd piles, state is now (0, 1, 1) - Take from 2nd and 3rd piles, state is now (0, 0, 0) There are fewer than two non-empty piles, so the game ends. Total: 6 points.
Example 2:
Input: a = 4, b = 4, c = 6 Output: 7 Explanation: The starting state is (4, 4, 6). One optimal set of moves is: - Take from 1st and 2nd piles, state is now (3, 3, 6) - Take from 1st and 3rd piles, state is now (2, 3, 5) - Take from 1st and 3rd piles, state is now (1, 3, 4) - Take from 1st and 3rd piles, state is now (0, 3, 3) - Take from 2nd and 3rd piles, state is now (0, 2, 2) - Take from 2nd and 3rd piles, state is now (0, 1, 1) - Take from 2nd and 3rd piles, state is now (0, 0, 0) There are fewer than two non-empty piles, so the game ends. Total: 7 points.
Example 3:
Input: a = 1, b = 8, c = 8 Output: 8 Explanation: One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty. After that, there are fewer than two non-empty piles, so the game ends.
Constraints:
1 <= a, b, c <= 105Problem Overview: You are given three piles containing a, b, and c stones. Each move removes one stone from two different non‑empty piles and increases the score by 1. The goal is to maximize the total score. The challenge is figuring out how long you can keep pairing stones from different piles before one or two piles run out.
Approach 1: Greedy Pairing with Max Heap (O((a+b+c) log 3) time, O(1) space)
This method directly simulates the process using a max heap (priority queue). Push the three pile sizes into the heap and repeatedly pop the two largest piles. Remove one stone from each, increase the score, then push the remaining counts back if they are still positive. The greedy insight is simple: always pair the two largest piles so the largest pile does not dominate and end the game early. Because the heap size never exceeds three elements, each operation is effectively constant, though technically O(log 3). This approach mirrors the real process and is easy to reason about, making it a common first implementation when practicing heap (priority queue) problems.
Approach 2: Mathematical Greedy Observation (O(1) time, O(1) space)
A key observation eliminates simulation entirely. Let the piles be a, b, and c, and assume c is the largest. Each move consumes exactly two stones total, so the maximum possible score cannot exceed (a + b + c) / 2. However, if the largest pile is bigger than the sum of the other two (c > a + b), the smaller piles run out first. In that case the score is limited to a + b. Otherwise, stones can be balanced across piles and the score reaches (a + b + c) / 2. The final answer is therefore min((a + b + c) / 2, a + b + c - max(a,b,c)). This reasoning combines ideas from greedy strategy and simple math constraints.
Recommended for interviews: The mathematical greedy approach is what interviewers usually expect. It shows you can recognize structural constraints instead of simulating every move. The heap solution is still useful because it demonstrates the greedy pairing intuition and works as a quick correctness check before deriving the constant‑time formula.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Pairing with Max Heap | O((a+b+c) log 3) | O(1) | When you want to simulate the process directly or practice priority queue operations |
| Mathematical Greedy Formula | O(1) | O(1) | Best for interviews and optimal solutions once the pairing constraint insight is recognized |