1753. Maximum Score From Removing Stones Solution

The problem

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 <= 10⁵

Approach overview

Problem 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 1: Greedy Pairing Strategy

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.

Python

def maxScore(a: int, b: int, c: int) -> int:
    stones = [a, b, c]
    stones.sort()
    if stones[2] >= stones[0] + stones[1]:
        return stones[0] + stones[1]
    return (a + b + c) // 2

print(maxScore(2, 4, 6))

Java

import java.util.Arrays;

public class StoneGame {
    public static int maxScore(int a, int b, int c) {
        int[] stones = {a, b, c};
        Arrays.sort(stones);
        if (stones[2] >= stones[0] + stones[1])
            return stones[0] + stones[1];
        return (a + b + c) / 2;
    }
    public static void main(String[] args) {
        int a = 2, b = 4, c = 6;
        System.out.println(maxScore(a, b, c));
    }
}

C++

#include <iostream>
#include <algorithm>
using namespace std;

int maxScore(int a, int b, int c) {
    int stones[] = {a, b, c};
    sort(stones, stones+3);
    if (stones[2] >= stones[0] + stones[1])
        return stones[0] + stones[1];
    return (a + b + c) / 2;
}

int main() {
    int a = 2, b = 4, c = 6;
    cout << maxScore(a, b, c) << endl;
    return 0;
}

JavaScript

function maxScore(a, b, c) {
    let stones = [a, b, c];
    stones.sort((x, y) => x - y);
    if (stones[2] >= stones[0] + stones[1])
        return stones[0] + stones[1];
    return Math.floor((a + b + c) / 2);
}

console.log(maxScore(2, 4, 6));

#include <stdio.h>

int maxScore(int a, int b, int c) {
    int max1, max2, max3;
    max1 = a > b ? (a > c ? a : c) : (b > c ? b : c);
    max3 = a < b ? (a < c ? a : c) : (b < c ? b : c);
    max2 = a + b + c - max1 - max3;
    
    if (max1 >= max2 + max3)
        return max2 + max3;
    else
        return (a + b + c) / 2;
}

int main() {
    int a = 4, b = 4, c = 6;
    printf("%d\n", maxScore(a, b, c));
    return 0;
}

using System;

public class StoneGame {
    public static int MaxScore(int a, int b, int c) {
        int[] stones = new int[] { a, b, c };
        Array.Sort(stones);
        if (stones[2] >= stones[0] + stones[1])
            return stones[0] + stones[1];
        return (a + b + c) / 2;
    }

    public static void Main() {
        int a = 2, b = 4, c = 6;
        Console.WriteLine(MaxScore(a, b, c));
    }
}

This Python solution sorts the list of piles, then evaluates if the largest pile can pair with the others more than their size. It calculates maximum possible pairs based on whether the condition holds, using integer division for final total score calculation.

Complexity

Time Complexity: O(1) - The sort operation is trivial for three elements.
Space Complexity: O(1) - A fixed-size list is used for computation.

Try this approach in the editor

Approach 2: Mathematical Approach to Pairing

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.

Python

def maxScore(a: int, b: int, c: int) -> int:
    total = a + b + c
    max1 = max(a, b, c)
    minSum = min(a, b, c)
    minSum = minSum + (total - max1 - minSum)
    return min(total // 2, minSum)

print(maxScore(2, 4, 6))

Java

public class StoneGame {
    public static int maxScore(int a, int b, int c) {
        int total = a + b + c;
        int max1 = Math.max(Math.max(a, b), c);
        int minSum = Math.min(a, b);
        minSum = minSum + (a + b + c - max1 - minSum);
        return Math.min(total / 2, minSum);
    }

    public static void main(String[] args) {
        System.out.println(maxScore(2, 4, 6));
    }
}

C++

#include <iostream>
#include <algorithm>
using namespace std;

int maxScore(int a, int b, int c) {
    int total = a + b + c;
    int max1 = max({a, b, c});
    int minSum = min({a, b, c});
    minSum += total - max1 - minSum;
    return min(total / 2, minSum);
}

int main() {
    cout << maxScore(2, 4, 6) << endl;
    return 0;
}

JavaScript

function maxScore(a, b, c) {
    const total = a + b + c;
    const max1 = Math.max(a, b, c);
    let minSum = Math.min(a, b, c);
    minSum += total - max1 - minSum;
    return Math.min(Math.floor(total / 2), minSum);
}

console.log(maxScore(2, 4, 6));

#include <stdio.h>

int maxScore(int a, int b, int c) {
    int total = a + b + c;
    int max1 = a > b ? (a > c ? a : c) : (b > c ? b : c);
    int minSum = a < b ? (a < c ? a : c) : (b < c ? b : c);
    minSum += a + b + c - max1 - minSum;
    return total / 2 < minSum ? total / 2 : minSum;
}

int main() {
    printf("%d\n", maxScore(2, 4, 6));
    return 0;
}

using System;

public class StoneGame {
    public static int MaxScore(int a, int b, int c) {
        int total = a + b + c;
        int max1 = Math.Max(a, Math.Max(b, c));
        int minSum = Math.Min(a, b);
        minSum += total - max1 - minSum;
        return Math.Min(total / 2, minSum);
    }

    public static void Main() {
        Console.WriteLine(MaxScore(2, 4, 6));
    }
}

Python here is used to quickly compute evaluations using a mathematical understanding of distribution limits versus possible pairings. This solution checks the feasibility against both pairing opportune outcomes and constraints imposed by pile distribution.

Complexity

Time Complexity: O(1) - Requires minimal computational steps.
Space Complexity: O(1) - Handles data computations without additional storage.

Try this approach in the editor

Approach 3: Default Approach

func maximumScore(a int, b int, c int) (ans int) {
	s := []int{a, b, c}
	sort.Ints(s)
	for s[1] > 0 {
		ans++
		s[1]--
		s[2]--
		sort.Ints(s)
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Pairing Strategy	Time Complexity: O(1) - The sort operation is trivial for three elements. Space Complexity: O(1) - A fixed-size list is used for computation.
Mathematical Approach to Pairing	Time Complexity: O(1) - Requires minimal computational steps. Space Complexity: O(1) - Handles data computations without additional storage.
Default Approach	–

Complexity analysis

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

Frequently asked questions

Is Maximum Score From Removing Stones easy or hard?

The problem is rated Medium on LeetCode. The heap simulation is straightforward, but identifying the mathematical limit that leads to the O(1) solution requires recognizing the greedy pairing constraint.

How to solve Maximum Score From Removing Stones in O(1)?

Compute the total stones S = a + b + c and the largest pile max(a,b,c). If the largest pile exceeds the sum of the other two, the score equals the total stones in the two smaller piles. Otherwise the maximum score is S / 2. The formula is min(S / 2, S - max(a,b,c)).

Maximum Score From Removing Stones Python or Java solution

Python, Java, C++, and other languages can implement the constant‑time formula easily using basic arithmetic. Many implementations also include a heap-based simulation using a priority queue to repeatedly remove stones from the two largest piles.

What is the best approach for Maximum Score From Removing Stones?

The optimal solution uses a mathematical greedy observation. The score cannot exceed half the total number of stones because each move removes two stones. If the largest pile is greater than the sum of the other two, the answer is the sum of the two smaller piles; otherwise it is (a + b + c) / 2. This produces an O(1) time and O(1) space solution.

Is Maximum Score From Removing Stones asked at Google/Amazon/Meta?

Greedy reasoning and small mathematical observations like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The exact problem may vary, but the pattern of pairing resources and analyzing limits is common in interview questions.

What data structure is used in Maximum Score From Removing Stones?

A max heap (priority queue) can be used to repeatedly select the two largest piles and remove one stone from each. However, the optimal approach avoids data structures entirely by applying a mathematical greedy formula based on the total stones and the largest pile.

What is the time complexity of Maximum Score From Removing Stones?

The optimal mathematical solution runs in O(1) time because it only performs a few arithmetic operations on the three pile sizes. A simulation using a max heap takes O((a+b+c) log 3) time since each move removes two stones and performs priority queue operations.

Maximum Score From Removing Stones solution and explanation

The problem

Approach overview

Approach 1: Greedy Pairing Strategy

Approach 2: Mathematical Approach to Pairing

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Score From Removing Stones solution and explanation

The problem

Approach overview

Approach 1: Greedy Pairing Strategy

Approach 2: Mathematical Approach to Pairing

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems