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.
This approach involves always taking stones from the two piles with the most stones. The idea is that to maximize the score, you should try to balance the piles as you play, by always taking from the two largest non-empty piles. This way, you maximize the number of pairs you can form before one of the piles becomes empty.
In this C solution, the code first determines the largest, second largest, and smallest pile sizes. It then checks if the largest pile has more stones than the sum of the other two. If so, the result is the sum of the smaller two piles. If not, the maximum score that can be obtained is half the total number of stones, as all stones can be paired optimally.
Time Complexity: O(1) - Constant time as the calculation involves basic arithmetic and comparisons.
Space Complexity: O(1) - Constant space as no additional data structures are used.
Instead of simulating each move, this approach formulates a mathematical strategy based on possible scenarios. If the sum of the two larger piles is greater than the largest pile, the result is half of the total stones. Otherwise, the score is determined by the sum of the two smaller piles.
This alternative C solution uses a mathematical method to determine whether pairing is inhibited by stone distribution across piles. The code calculates the total stones and compares if pairing is limited by the count in the smallest piles or simply the total/2.
Time Complexity: O(1) - Constant arithmetic operations.
Space Complexity: O(1) - No additional memory allocations.
| Approach | Complexity |
|---|---|
| Greedy Pairing Strategy | Time Complexity: O(1) - Constant time as the calculation involves basic arithmetic and comparisons. |
| Mathematical Approach to Pairing | Time Complexity: O(1) - Constant arithmetic operations. |
| Default Approach | — |
| 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 |
Maximum Score From Removing Stones💯 | Leetcode 1753 | AlgoMaster Sheet STL #4 | FAANG || CS FOR ALL • CS FOR ALL • 1,481 views views
Watch 9 more video solutions →Practice Maximum Score From Removing Stones with our built-in code editor and test cases.
Practice on FleetCode