NeetCode #211LC-948MediumTwo Pointers
← Back to All Problems#211 · #948 · Bag of Tokens(令牌放置)
📌 Problem Statement & Constraints
You start with
power tokens and score = 0. You may play a token face up if you have at least tokens[i] power (gaining 1 score and losing that much power), or face down if your score is at least 1 (gaining tokens[i] power and losing 1 score). Each token may be used at most once. Return the maximum possible score. Constraints: 0 <= tokens.length <= 1000, 0 <= power, tokens[i] < 10^4.💡 Core Algorithmic Approaches
- Sort the tokens. Face-up plays consume the cheapest tokens and gain score; face-down plays sacrifice score for the most expensive tokens.
- Two pointers: the left pointer points at the cheapest unused token and the right pointer at the most expensive.
- If you can afford
tokens[l], play it face up (score up, power down,ladvances). Otherwise, if you have score, playtokens[r]face down (power up, score down,radvances). If neither is possible, stop. - The answer is the maximum score ever reached, not necessarily the final score, since score can be spent later.
💻 Benchmark Python3 Implementation
class Solution:
def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
tokens.sort()
l, r = 0, len(tokens) - 1
score = 0
best = 0
while l <= r:
if power >= tokens[l]:
power -= tokens[l] # play face up
score += 1
l += 1
best = max(best, score)
elif score > 0:
power += tokens[r] # play face down
score -= 1
r -= 1
else:
break # no move available
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates; the two-pointer scan is O(n).
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Returning
scoreinstead ofbest: the final score may be lower than the peak, because score is spent to gain power. - Playing the most expensive token face up: the cheapest affordable token should be used, to conserve power.
- Playing a token face down when power suffices: face-up gains score, which is always preferable when affordable.
- Not sorting: the greedy choices depend on the ordering by cost.
- Forgetting the break when neither move is possible: without it, the loop would spin.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.