⚡Flashcard Drill➔
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

  1. Sort the tokens. Face-up plays consume the cheapest tokens and gain score; face-down plays sacrifice score for the most expensive tokens.
  2. Two pointers: the left pointer points at the cheapest unused token and the right pointer at the most expensive.
  3. If you can afford tokens[l], play it face up (score up, power down, l advances). Otherwise, if you have score, play tokens[r] face down (power up, score down, r advances). If neither is possible, stop.
  4. 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 score instead of best: 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.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems