MediumNo. 1753
Maximum Score From Removing Stones — LeetCode 1753 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Math, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
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.
Example
- Input
- a = 2, b = 4, c = 6
- Output
- 6
- Explanation
- The starting state is (2, 4, 6). One optimal set of moves is:
Python solution
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 ansComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1753. Maximum Score From Removing Stones is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1686 | Stone Game VI | Medium |
| 0420 | Strong Password Checker | Hard |
| 0502 | IPO | Hard |
| 0630 | Course Schedule III | Hard |
| 0670 | Maximum Swap | Medium |
| 0738 | Monotone Increasing Digits | Medium |
Frequently asked questions
- How hard is LeetCode 1753. Maximum Score From Removing Stones?
LeetCode 1753. Maximum Score From Removing Stones is rated Medium on LeetCode.
- What topics does LeetCode 1753. Maximum Score From Removing Stones cover?
LeetCode 1753. Maximum Score From Removing Stones is tagged Greedy, Math and Heap (Priority Queue) on LeetCode.