#1753

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Score From Removing Stones

Maximize the score in a solitaire game by optimally removing stones from three piles with a greedy approach.

Problem Statement

You are playing a game with three piles of stones, denoted by a, b, and c, where each pile contains a positive number of stones. On each turn, you pick two different non-empty piles, remove one stone from each, and score 1 point. The game continues until fewer than two piles contain stones.

Given the sizes of the three piles, a, b, and c, your goal is to return the maximum score you can achieve by optimally removing stones from the piles.

Examples

Example 1

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

Output: 6

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

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

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 <= 105

Solution Approach

Greedy Choice with Priority Queue

The best approach is to always remove stones from the two largest piles in order to maximize the total score. A priority queue (heap) can be used to efficiently track the sizes of the piles and ensure you always have access to the largest two piles.

Heap-based Simulation

By simulating the stone removal process with a heap, we ensure that each move is made optimally. At every step, we extract the two largest piles, reduce their sizes, and push them back into the heap. This process continues until fewer than two piles contain stones.

Edge Case Handling

In cases where one pile is much larger than the others, the greedy choice remains effective. However, when all piles become roughly equal, the game will end when no further valid moves are possible.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is dominated by the heap operations, which take O(log 3) per move, effectively constant. Space complexity is O(1), as we only need a fixed number of variables to track the piles.

What Interviewers Usually Probe

The candidate effectively uses a greedy approach for optimal moves.
They demonstrate understanding of heap operations to solve the problem efficiently.
They correctly handle the edge case of one pile being much larger than the others.

Common Pitfalls or Variants

Common pitfalls

Not using a heap to efficiently track the largest piles.
Failing to account for the situation where fewer than two piles remain.
Overcomplicating the problem by not recognizing the greedy approach.

Follow-up variants

Generalize to more than three piles of stones.
Consider adding additional rules to the game, such as different scoring based on pile sizes.
Modify the game to allow removing stones from any number of piles in each move.

FAQ

How do I approach the Maximum Score From Removing Stones problem?

You should apply a greedy approach where you always remove stones from the two largest piles to maximize the score.

Can I solve this problem without using a heap?

Yes, but using a heap allows you to manage the largest piles efficiently, making the solution optimal.

What is the time complexity of the solution?

The time complexity is O(log 3) for each heap operation, which is effectively constant for this problem.

How do I handle the edge case where one pile is much larger than the others?

Even in such cases, the greedy approach of always removing stones from the two largest piles remains optimal.

What is the most efficient way to implement this solution?

The most efficient implementation uses a priority queue (heap) to always access the two largest piles for each move.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        s = sorted([a, b, c])
        ans = 0
        while s[1]:
            ans += 1
            s[1] -= 1
            s[2] -= 1
            s.sort()
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        s = sorted([a, b, c])
        ans = 0
        while s[1]:
            ans += 1
            s[1] -= 1
            s[2] -= 1
            s.sort()
        return ans

Continue Practicing

#1686 stone game vi #1648 sell diminishing valued colored balls #1739 building boxes