LeetCode 1753 - Maximum Score From Removing Stones

The problem is a combinatorial game involving three piles of stones with counts a, b, and c. In each move, you are allowed to pick two different non-empty piles and remove one stone from each, earning 1 point per move. The game ends when fewer than two piles have stones left.

leetcodemediummathgreedyheap-(priority-queue)

LeetCode Problem 1753

Difficulty: 🟡 Medium
Topics: Math, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem is a combinatorial game involving three piles of stones with counts a, b, and c. In each move, you are allowed to pick two different non-empty piles and remove one stone from each, earning 1 point per move. The game ends when fewer than two piles have stones left. The goal is to compute the maximum score possible by performing these moves optimally.

The input consists of three integers a, b, and c, each representing the number of stones in a pile. The output is a single integer representing the maximum score achievable. The constraints 1 <= a, b, c <= 10^5 tell us that the solution must be efficient, ideally O(1) or O(log n), since iterating through each stone individually could be too slow.

Key observations include the fact that a move always decreases the total number of stones by 2, and you can only pair stones from two piles at a time. Edge cases to consider include when one pile is much larger than the sum of the other two, or when all piles have equal numbers.

Approaches

The brute-force approach involves simulating the game directly: repeatedly pick the two largest piles, remove one stone from each, and add 1 to the score until fewer than two piles remain non-empty. This guarantees correctness because each move is valid, but it is inefficient: if the sum of all stones is up to 3×10^5, repeatedly selecting piles and updating counts is slow.

The key insight for an optimal solution is based on sorting and mathematical reasoning. Let x ≤ y ≤ z be the sizes of the piles after sorting. The maximum number of moves is bounded by either x + y (if the largest pile is larger than the sum of the other two, the extra stones cannot form pairs) or (a + b + c) // 2 (since each move removes 2 stones, you cannot score more than half of the total stones). This gives a direct formula:

max_score = min(a + b, a + c, b + c, (a + b + c) // 2)

This formula eliminates the need for simulation and runs in constant time.

Approach Time Complexity Space Complexity Notes
Brute Force O(a + b + c) O(1) Simulate each move by selecting two largest piles repeatedly
Optimal O(1) O(1) Use sorting or max-min logic to compute min(a + b, a + c, b + c, (a + b + c) // 2)

Algorithm Walkthrough

  1. Take the input integers a, b, and c.
  2. Sort the three numbers to get x ≤ y ≤ z. This helps reason about the largest pile relative to the others.
  3. Calculate the sum of all stones total = a + b + c.
  4. Compute the sum of the two smallest piles x + y.
  5. The maximum score is the minimum of x + y and total // 2. This ensures that you do not remove more stones than exist, and also accounts for the fact that moves require two stones.
  6. Return this value as the result.

Why it works: Sorting ensures that x + y is always the number of moves possible if z is extremely large. Taking min(x + y, total // 2) guarantees that we do not exceed the number of stones available for pairing. This invariant guarantees correctness for any valid input.

Python Solution

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        piles = sorted([a, b, c])
        x, y, z = piles
        return min(x + y, (a + b + c) // 2)

Implementation explanation: First, we sort the piles to determine which is the largest and which are the smaller ones. x + y represents the maximum possible moves when the largest pile may dominate. (a + b + c) // 2 represents the absolute upper bound because each move consumes two stones. Returning the minimum of these ensures we respect both constraints.

Go Solution

func maximumScore(a int, b int, c int) int {
    // Sort a, b, c using simple comparisons
    if a > b {
        a, b = b, a
    }
    if b > c {
        b, c = c, b
    }
    if a > b {
        a, b = b, a
    }
    if a+b < (a+b+c)/2 {
        return a + b
    }
    return (a + b + c) / 2
}

Go-specific notes: Since Go does not have a built-in sort for three integers, we manually sort using conditional swaps. The rest follows the same logic as the Python solution, ensuring we do not exceed either x + y or total // 2.

Worked Examples

Example 1: a = 2, b = 4, c = 6

Sorted: x = 2, y = 4, z = 6

  • x + y = 6
  • (a + b + c) // 2 = (2 + 4 + 6) // 2 = 6

Maximum score = min(6, 6) = 6

Example 2: a = 4, b = 4, c = 6

Sorted: x = 4, y = 4, z = 6

  • x + y = 8
  • (a + b + c) // 2 = (4 + 4 + 6) // 2 = 7

Maximum score = min(8, 7) = 7

Example 3: a = 1, b = 8, c = 8

Sorted: x = 1, y = 8, z = 8

  • x + y = 9
  • (a + b + c) // 2 = (1 + 8 + 8) // 2 = 8

Maximum score = min(9, 8) = 8

Complexity Analysis

Measure Complexity Explanation
Time O(1) Sorting three numbers is constant time and min calculation is constant
Space O(1) Only a fixed number of variables are used

The algorithm is extremely efficient and handles the largest input values within the problem constraints.

Test Cases

# Provided examples
assert Solution().maximumScore(2, 4, 6) == 6  # Balanced piles
assert Solution().maximumScore(4, 4, 6) == 7  # Largest pile dominates
assert Solution().maximumScore(1, 8, 8) == 8  # One small pile, two large piles

# Edge cases
assert Solution().maximumScore(1, 1, 1) == 1  # All piles equal, smallest non-trivial case
assert Solution().maximumScore(100000, 100000, 100000) == 150000  # Maximal equal piles
assert Solution().maximumScore(1, 100000, 100000) == 100000  # Small pile with large ones
assert Solution().maximumScore(1, 2, 3) == 3  # Incremental small piles
Test Why
2, 4, 6 Normal case with different pile sizes
4, 4, 6 Largest pile exceeds sum of smaller piles
1, 8, 8 One very small pile, tests limiting factor
1, 1, 1 Minimal equal piles
100000, 100000, 100000 Max input values to test efficiency
1, 100000, 100000 Large disparity between piles
1, 2, 3 Small incremental piles

Edge Cases

1. Large disparities: When one pile is much larger than the sum of the other two, it cannot contribute to more moves. The solution correctly limits the maximum score to x + y.

2. Equal piles: When all piles are equal, each move can be made by pairing any two piles. The formula still correctly computes total // 2 as the maximum number of moves.

3. Minimal input values: If piles are all 1, the solution handles it and returns 1. This ensures that the edge of the constraints does not cause an off-by-one error.

4. Maximum input values: Piles at 10^5 test integer overflow in languages with fixed-size integers. Python handles it naturally, and in Go, integer division and addition remain safe within 32-bit int limits for these values.