MediumNo. 2029
Stone Game IX — LeetCode 2029 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Math, Counting, Game Theory
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value.
Example
- Input
- stones = [2,1]
- Output
- true
- Explanation
- The game will be played as follows:
Python solution
class Solution:
def stoneGameIX(self, stones: List[int]) -> bool:
def check(cnt: List[int]) -> bool:
if cnt[1] == 0:
return False
cnt[1] -= 1
r = 1 + min(cnt[1], cnt[2]) * 2 + cnt[0]
if cnt[1] > cnt[2]:
cnt[1] -= 1
r += 1
return r % 2 == 1 and cnt[1] != cnt[2]
c1 = [0] * 3
for x in stones:
c1[x % 3] += 1
c2 = [c1[0], c1[2], c1[1]]
return check(c1) or check(c2)Complexity
- Time
- O(n)where n is the length of the array stones
- Space · auxiliary
- O(1)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 2029. Stone Game IX is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0877 | Stone Game | Medium |
| 1561 | Maximum Number of Coins You Can Get | Medium |
| 1686 | Stone Game VI | Medium |
| 2038 | Remove Colored Pieces if Both Neighbors are the Same Color | Medium |
| 0910 | Smallest Range II | Medium |
| 0945 | Minimum Increment to Make Array Unique | Medium |
Frequently asked questions
- How hard is LeetCode 2029. Stone Game IX?
LeetCode 2029. Stone Game IX is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2029. Stone Game IX?
The Python solution on this page runs in O(n), where n is the length of the array \textit{stones}.
- What is the space complexity of LeetCode 2029. Stone Game IX?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2029. Stone Game IX cover?
LeetCode 2029. Stone Game IX is tagged Greedy, Array, Math, Counting and Game Theory on LeetCode.