566. Bag of Tokens
You have a bag of tokens, where tokens[i] is the value of the i-th token, and you start with power power and a score of 0.
Each token can be played at most once, in any order you like, in one of two ways:
- Face up — allowed only if your current power is at least
tokens[i]: you losetokens[i]power and gain 1 score. - Face down — allowed only if your current score is at least 1: you lose 1 score and gain
tokens[i]power.
You are not required to play every token. Return the maximum score you can ever hold at any point.
Example 1:
Input: tokens = [100], power = 50
Output: 0
Explanation: With 50 power you cannot afford the only token face up, and with 0 score you cannot play it face down. The score stays 0.
Example 2:
Input: tokens = [200, 100], power = 150
Output: 1
Explanation: Play the 100 token face up (power 150 → 50, score 1). The 200 token is unaffordable, and trading the score away for power would leave nothing to buy — stop at score 1.
Example 3:
Input: tokens = [100, 200, 300, 400], power = 200
Output: 2
Explanation: Face up 100 (power 100, score 1) → face down 400 (power 500, score 0) → face up 200 (power 300, score 1) → face up 300 (power 0, score 2).
Constraints:
- 1 ≤ tokens.length ≤ 1000
- 0 ≤ tokens[i], power ≤ 10⁴
Hints:
Score is the currency that matters; power is just fuel. When you buy score, buy it as cheaply as possible — when you sell score for power, sell it for as much as possible.
Sort the tokens. Keep two pointers: buy from the cheap end face up whenever you can afford it, and only when stuck, cash in one score for the most expensive remaining token.
Two guard rails: never sell your last chance (a face-down play with only one token left is pure loss), and remember the running maximum — the final score can be lower than the best score you passed through.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: tokens = [100], power = 50
Expected output: 0