Problem Description

You have three piles of stones with sizes a, b, and c. In each turn of the game, you must:

• Choose two different non-empty piles
• Remove one stone from each of the two chosen piles
• Add 1 point to your score

The game continues until you cannot make a valid move anymore (when fewer than two piles have stones remaining).

Your goal is to find the maximum possible score you can achieve by making optimal moves.

For example, if you have piles of sizes a = 2, b = 4, and c = 6:

• You could take stones from piles b and c, leaving you with (2, 3, 5) and scoring 1 point
• Continue taking from the two largest piles to maximize your score
• The game ends when at most one pile has stones remaining

The solution approach repeatedly takes stones from the two largest piles. By sorting the piles after each move and always choosing the two largest piles (indices 1 and 2 in the sorted array), we ensure we can make the maximum number of moves possible. The algorithm continues until the middle pile becomes empty, at which point we can no longer make valid moves since we need at least two non-empty piles.

Intuition

The key insight is to think about when the game ends and work backwards. The game stops when we have at most one non-empty pile. This means we want to distribute our moves in a way that uses up the stones as evenly as possible.

Consider what happens if one pile is much larger than the others. If pile c is huge while a and b are small, we'll quickly exhaust a and b, leaving many stones unused in c. This limits our score.

The optimal strategy is to always take stones from the two largest piles. Why? By repeatedly reducing the largest piles, we prevent any single pile from becoming too dominant. This keeps all piles relatively balanced, allowing us to continue making moves for as long as possible.

Think of it like balancing water levels in three containers - if we always drain from the two fullest containers, we maximize the time before one runs dry.

Mathematically, the maximum score is actually min(sum(a, b, c) / 2, a + b + c - max(a, b, c)). The first part sum/2 represents the theoretical maximum if we could perfectly pair all stones. The second part handles the case where one pile is larger than the sum of the other two - in this case, we're limited by the smaller piles.

The greedy approach of always choosing the two largest piles naturally achieves this maximum. By sorting after each move and selecting piles at indices 1 and 2, we ensure we're always making the optimal choice that keeps the piles as balanced as possible.

Learn more about Greedy, Math and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a greedy algorithm with sorting to maintain the optimal selection of piles at each step.

Data Structure: We use a list s to store the three pile sizes, which allows us to sort them repeatedly.

Algorithm Steps:

1. Initialize: Create a sorted list s = sorted([a, b, c]) so that s[0] ≤ s[1] ≤ s[2]. This ensures we have the piles ordered from smallest to largest.

2. Main Loop: Continue while s[1] > 0 (the middle pile is non-empty):

   • Why check s[1]? If the middle pile is empty, then the smallest pile s[0] must also be empty (since they're sorted), meaning we have at most one non-empty pile and cannot make valid moves.

3. Make a Move: In each iteration:

   • Increment the answer counter: ans += 1
   • Remove one stone from the two largest piles: s[1] -= 1 and s[2] -= 1
   • Re-sort the list: s.sort()

4. Re-sorting Logic: After taking stones from piles at positions 1 and 2, the ordering might change. For example, if we had [1, 3, 5] and took from the larger two, we'd get [1, 2, 4]. The sorting ensures we always identify the correct two largest piles for the next move.

5. Return: When the loop exits (middle pile becomes 0), return ans as the maximum score.

Time Complexity: O(n log n) where n is the total number of moves (maximum of (a+b+c)/2). Each iteration involves sorting 3 elements, which is O(1), but we do this n times.

Space Complexity: O(1) as we only use a fixed-size list of 3 elements.

The beauty of this approach is its simplicity - by always maintaining sorted order and greedily selecting the two largest piles, we automatically achieve the maximum possible score without complex calculations.

Example Walkthrough

Let's trace through the algorithm with piles a = 2, b = 4, and c = 6.

Initial Setup:

• Start with s = sorted([2, 4, 6]) = [2, 4, 6]
• Score = 0

Move 1:

• Check: s[1] = 4 > 0 ✓ (can continue)
• Take from two largest piles: s[1] = 4-1 = 3, s[2] = 6-1 = 5
• Current state: [2, 3, 5]
• Sort: [2, 3, 5] (already sorted)
• Score = 1

Move 2:

• Check: s[1] = 3 > 0 ✓
• Take from two largest: s[1] = 3-1 = 2, s[2] = 5-1 = 4
• Current state: [2, 2, 4]
• Sort: [2, 2, 4]
• Score = 2

Move 3:

• Check: s[1] = 2 > 0 ✓
• Take from two largest: s[1] = 2-1 = 1, s[2] = 4-1 = 3
• Current state: [2, 1, 3]
• Sort: [1, 2, 3]
• Score = 3

Move 4:

• Check: s[1] = 2 > 0 ✓
• Take from two largest: s[1] = 2-1 = 1, s[2] = 3-1 = 2
• Current state: [1, 1, 2]
• Sort: [1, 1, 2]
• Score = 4

Move 5:

• Check: s[1] = 1 > 0 ✓
• Take from two largest: s[1] = 1-1 = 0, s[2] = 2-1 = 1
• Current state: [1, 0, 1]
• Sort: [0, 1, 1]
• Score = 5

Move 6:

• Check: s[1] = 1 > 0 ✓
• Take from two largest: s[1] = 1-1 = 0, s[2] = 1-1 = 0
• Current state: [0, 0, 0]
• Sort: [0, 0, 0]
• Score = 6

Termination:

• Check: s[1] = 0 (not > 0) ✗
• Game ends with final score = 6

Notice how by always taking from the two largest piles, we avoided depleting any pile too quickly. This balanced approach allowed us to make 6 moves total, which equals (2+4+6)/2 = 6, the theoretical maximum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(min(a, b, c) * log 3) which simplifies to O(min(a, b, c))

The code uses a while loop that continues until s[1] becomes 0. In each iteration:

• Two elements are decremented by 1 (s[1] and s[2])
• The array is sorted using s.sort(), which takes O(log 3) = O(1) time for a fixed-size array of 3 elements

The loop runs at most min(a, b, c) times because:

• After sorting, s[0] ≤ s[1] ≤ s[2]
• Each iteration decrements the two larger values
• The loop terminates when the middle element s[1] reaches 0
• The maximum number of iterations occurs when we can pair the smallest pile with others until it's exhausted

Therefore, the overall time complexity is O(min(a, b, c) * 1) = O(min(a, b, c))

Space Complexity: O(1)

The code uses:

• A fixed-size list s containing 3 elements
• A single integer variable ans

No additional space that scales with input size is used, resulting in constant space complexity O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Re-sort After Each Move

One of the most common mistakes is taking stones from the two largest piles but forgetting to re-sort the array afterward. This leads to incorrect pile selection in subsequent iterations.

Incorrect Implementation:

def maximumScore(self, a: int, b: int, c: int) -> int:
    piles = sorted([a, b, c])
    score = 0
  
    while piles[1] > 0:
        score += 1
        piles[1] -= 1
        piles[2] -= 1
        # MISSING: piles.sort() - This will cause wrong selections!
  
    return score

Why it fails: After removing stones, the relative sizes change. For example, starting with [2, 5, 6], after one move we have [2, 4, 5]. Without sorting, the next iteration would incorrectly modify indices 1 and 2 again, giving [2, 3, 4], when it should select the actual two largest piles.

Solution: Always sort after each modification to maintain the invariant that piles[0] ≤ piles[1] ≤ piles[2].

2. Incorrect Termination Condition

Another pitfall is using the wrong condition to determine when the game ends.

Incorrect Implementations:

# Wrong: Checking only the largest pile
while piles[2] > 0:  # Game might end earlier!
  
# Wrong: Checking the smallest pile
while piles[0] > 0:  # Game continues even after this!
  
# Wrong: Checking if we can make exactly one more move
while piles[1] > 0 and piles[2] > 0:  # Redundant check

Why checking piles[1] > 0 is correct: When the middle pile becomes 0, we know:

• The smallest pile piles[0] must also be 0 (due to sorting)
• We have at most one non-empty pile (the largest)
• We cannot make valid moves with fewer than 2 non-empty piles

3. Attempting to Optimize by Taking From Different Piles

Some might think taking from the smallest and largest pile could be beneficial in certain cases to "balance" the piles.

Incorrect Strategy:

def maximumScore(self, a: int, b: int, c: int) -> int:
    piles = sorted([a, b, c])
    score = 0
  
    while piles[1] > 0:
        score += 1
        # Wrong: Trying to "balance" by taking from smallest and largest
        if piles[2] - piles[0] > piles[1]:
            piles[0] -= 1
            piles[2] -= 1
        else:
            piles[1] -= 1
            piles[2] -= 1
        piles.sort()
  
    return score

Why it's wrong: The greedy approach of always taking from the two largest piles is mathematically optimal. Trying to balance piles can actually reduce the total number of moves possible.

4. Integer Overflow in Mathematical Solution

When using the optimized mathematical formula, be careful with the order of operations.

Potential Issue:

# In some languages, this might overflow for large values
return min((a + b + c) // 2, a + b + c - max(a, b, c))

Better Approach:

def maximumScore(self, a: int, b: int, c: int) -> int:
    total = a + b + c
    max_pile = max(a, b, c)
  
    # Store intermediate results to avoid recalculation
    return min(total // 2, total - max_pile)

5. Not Handling Edge Cases

While the problem typically guarantees non-negative inputs, it's good practice to consider edge cases:

Robust Implementation:

def maximumScore(self, a: int, b: int, c: int) -> int:
    # Handle edge case where all piles are 0
    if a == 0 and b == 0 and c == 0:
        return 0
  
    # Handle case where only one pile has stones
    non_zero_count = sum(1 for x in [a, b, c] if x > 0)
    if non_zero_count < 2:
        return 0
  
    # Proceed with normal algorithm
    total = a + b + c
    max_pile = max(a, b, c)
    return min(total // 2, total - max_pile)