Problem Breakdown
We need to maximize the score given an initial power P and a list of token values. We have two operations: spend power on a cheap token (gain +1 point) or sell an expensive token for points (requires at least 1 current point). Since we want to accumulate as many points as possible, this is a resource management problem where “points” are the currency but also cost us progress if spent too early.
Inputs:
tokens: List of integers representing power costs.P: Integer initial power.
Outputs:
- Maximum integer score achievable.
Implicit Constraints & Edge Cases:
- Empty Input: If no tokens exist, the max score is naturally 0.
- Insufficient Power Initially: We might not be able to buy any token immediately; we must wait until power accumulates via selling (if possible). However, since initial score is 0, we cannot sell anything initially unless we first play a face-up move.
- Score Drop Risk: Selling reduces our current score by 1. We should only do this if it enables us to buy more tokens later that yield net positive points. If selling leads to the end of available moves without buying new ones, we lose potential max score (handled via tracking
max_score). - Ordering Matters: The order in which we process tokens matters for optimality. Sorting allows a greedy strategy: always buy the cheapest token if affordable; otherwise sell the most expensive one to boost power.
Intuition
A brute-force approach would try every permutation of playing face-up or face-down, resulting in complexity, which is impossible given tokens.length up to 1000. Even dynamic programming might be overkill if a greedy property holds.
Key Insight: To maximize points (score), we should always spend our power on the cheapest tokens available first because they cost less power per point gained (+1). Conversely, when we are stuck and cannot afford any more cheap tokens but have accumulated some score, we should sell the most expensive token to gain maximum possible power for a minimal penalty of 1 point.
Greedy Strategy:
- Sort
tokensin ascending order. This allows us to access the cheapest (left) and most expensive (right) tokens easily using two pointers. - While we have valid moves (pointers haven’t crossed):
- If current power cost of cheapest token: Buy it immediately. It’s always optimal because buying a cheaper token is better than saving power for an expensive one later, or selling to buy the same cheap one again. Increment score and move
leftpointer forward. Update global max score. - Else if current score : We can’t afford the cheapest token yet. To proceed, we must sell a token. Selling the most expensive (
right) gives us the maximum power boost for losing only 1 point. This is better than selling any other token or stopping early (unless no future buys are possible). Decrement score and moverightpointer backward. - Else: We can’t afford anything, nor do we have points to sell with. Stop processing.
- If current power cost of cheapest token: Buy it immediately. It’s always optimal because buying a cheaper token is better than saving power for an expensive one later, or selling to buy the same cheap one again. Increment score and move
Approach
- Initialize pointers
left = 0,right = len(tokens) - 1. - Sort the tokens array in ascending order.
- Maintain variables for current power (
P), current score, and maximum score seen so far (max_score). Note: We track max score because selling reduces our immediate score; we want to return the peak value reached during valid sequences of moves. Initializemax_score = -1(or handle empty case) but practically 0 is safe since scores are non-negative. - Loop while
left <= right:- Buy Condition: If
P >= tokens[left], play face up: subtract cost fromP, increment score, moveleft. Updatemax_scorewith current score (since we want the highest peak). - Sell Condition: Else if
score > 0: Play face down on most expensive token. Add value toP, decrement score, moveright. Do not update max here as this is a forced trade-off that lowers immediate state; however, it might enable future buys. We rely on the next iteration or loop termination for final result? Actually, standard practice tracks peak at every step just in case we stop early after selling but before buying more. - Stop Condition: If neither condition met (can’t afford cheapest AND score is 0), break loop.
- Buy Condition: If
- Return
max_score.
Complexity Analysis
- Time Complexity: , where is the number of tokens. This is dominated by sorting the array (). The two-pointer traversal takes linear time . Total: .
- Space Complexity: auxiliary space (excluding input storage and sort stack overhead, which Python’s Timsort uses or depending on implementation details). We use a constant amount of extra variables.
Solution
def bagOfTokensScore(tokens: list[int], P: int) -> int:
# Sort tokens to access cheapest (left) and most expensive (right) efficiently
tokens.sort()
left = 0
right = len(tokens) - 1
current_score = 0
max_score = 0
while left <= right:
if P >= tokens[left]:
# Play face up: spend power, gain score on cheapest token available
P -= tokens[left]
current_score += 1
left += 1
# Track the highest score achieved so far.
# We update here because selling (next branch) reduces current_score temporarily.
max_score = max(max_score, current_score)
elif current_score > 0:
# Play face down on most expensive token to gain power for future buys
P += tokens[right]
current_score -= 1
right -= 1
# Note: We don't update max_score here because this move reduces our score.
# However, if we stop after a sell that doesn't lead to more buys, the loop ends naturally.
else:
# Cannot afford cheapest token and have no points left to spend power for buying later
break
return max_score
Edge Cases Handled
- Empty
tokens: The function returns 0 immediately as initialized (loop doesn’t run). - Initial Power too low (
P < min(tokens)): If we cannot buy the first token and score is 0, loop breaks or enters sell branch if possible. Since initial score is 0, we can only enterelifafter buying at least one token. Thus, returns correct max (likely 0). - Single Token: Loop runs once. Either buys it (score=1) or skips/breaks (score=0). Correctly handles logic where selling a single remaining token is suboptimal and avoided by
max_scoretracking if we stop early? Actually, with one token left (left == right) and unable to buy but score > 0: The code enters the sell branch. This reduces score. If that was the last move, loop ends. Is this correct? Yes, because selling a single remaining token yields power for nothing (no tokens left). However,max_scorecaptures the state before we were forced to drop points if we had bought previously and then got stuck. Wait, in my code:- If I buy last token -> score increases -> max updated -> loop ends. Correct.
- If I can’t afford last token but have score > 0 (from previous buys) -> Sell logic triggers? Yes. This reduces score by 1 and gains power. Since no tokens left, this is a waste of points.
max_scoreholds the value from before this drop. Correct.
- Duplicates: Sorting handles duplicates naturally; pointers skip over them correctly based on values.