948 - Bag of Tokens

Difficulty: Medium | Pattern: Greedy + Two Pointers | Company tags: Google, Amazon

Problem Statement

You have an initial power of power, and 0 points. You have an array tokens where tokens[i] is the value of the i-th token (0-indexed).

You want to maximize the total number of points.

In one move you can play an unplayed token:

• Face-up: If your current power is at least tokens[i], pay tokens[i] power and gain 1 point.
• Face-down: If your current points are at least 1, pay 1 point and gain tokens[i] power.

Return the maximum number of points you can achieve after playing any number of tokens.

Example 1:

Input: tokens = [100], power = 50
Output: 0  (can't afford the token)

Example 2:

Input: tokens = [100,200], power = 150
Output: 1  (play token[0] face-up, gain 1 point)

Example 3:

Input: tokens = [100,200,300,400], power = 200
Output: 2

Approach: Greedy Sort + Two Pointers — O(n log n)

Key insight: Sort tokens. Play cheapest token face-up (spend power, gain point) and most expensive face-down (spend point, gain power). Use two pointers.

def bagOfTokensScore(tokens: list[int], power: int) -> int:
    tokens.sort()
    left, right = 0, len(tokens) - 1
    points = 0
    max_points = 0
    
    while left <= right:
        if power >= tokens[left]:
            power -= tokens[left]
            points += 1
            left += 1
            max_points = max(max_points, points)
        elif points > 0:
            power += tokens[right]
            points -= 1
            right -= 1
        else:
            break
    
    return max_points

Dry Run

tokens = [100,200,300,400], power = 200

left	right	power	points	action
0	3	200	0	200 gte 100 → spend 100, gain pt → power=100, pts=1
1	3	100	1	100 lt 200 but pts=1 → spend pt, gain 400 → power=500, pts=0
1	2	500	0	500 gte 200 → spend 200, gain pt → power=300, pts=1
2	2	300	1	300 gte 300 → spend 300, gain pt → power=0, pts=2
3	2			left gt right, stop

max_points = 2 ✓

Complexity

• Time: O(n log n)
• Space: O(1)