Bag of Tokens - Practice Coding Problems

Bag of Tokens - Problem

You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of token i.

Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):

Face-up: If your current power is at least tokens[i], you may play token i, losing tokens[i] power and gaining 1 score.

Face-down: If your current score is at least 1, you may play token i, gaining tokens[i] power and losing 1 score.

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

Input & Output

Example 1 — Basic Strategy

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

› Output: 2

💡 Note: Play token 100 face-up (power becomes 100, score becomes 1), then play token 200 face-up (power becomes -100, but we had enough initially), so we can get score 2 by playing tokens 100 and 200 face-up when we had enough power.

Example 2 — Face-down Strategy

$ Input: tokens = [100], power = 50

› Output: 0

💡 Note: We don't have enough power (50) to play the token (100) face-up, and we don't have any score to play it face-down, so maximum score is 0.

Example 3 — Mixed Strategy

$ Input: tokens = [200,100], power = 150

› Output: 1

💡 Note: Sort tokens to [100,200]. Play token 100 face-up (power becomes 50, score becomes 1). We can't play 200 face-up as we don't have enough power, so max score is 1.

Constraints

0 ≤ tokens.length ≤ 1000
0 ≤ tokens[i], power < 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

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

Strategy

Sort tokens and use two pointers for optimal play

Output

Maximum possible score = 2

Key Takeaway

🎯 Key Insight: Sort tokens first, then greedily play cheapest face-up and most expensive face-down for optimal score

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to sort tokens and use a greedy two-pointer approach: play the cheapest tokens face-up to maximize score, and play the most expensive tokens face-down when we need more power. Best approach is greedy with sorting. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Two Pointers	O(n log n)	O(1)	Sort tokens and greedily play cheapest face-up, most expensive face-down
Brute Force - Try All Combinations	O(3ⁿ)	O(n)	Recursively try playing each token face-up or face-down

Greedy with Two Pointers — Algorithm Steps

Sort tokens in ascending order
Use left pointer for cheapest tokens (face-up play)
Use right pointer for most expensive tokens (face-down play)
Greedily maximize score by optimal token selection

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Tokens

Arrange tokens from cheapest to most expensive

Two Pointers

Left for face-up (cheap), right for face-down (expensive)

Greedy Choice

Maximize score by optimal token selection

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* tokens, int n, int power) {
    qsort(tokens, n, sizeof(int), compare);
    int left = 0, right = n - 1;
    int score = 0;
    int maxScore = 0;
    
    while (left <= right) {
        // If we can play the cheapest token face-up
        if (power >= tokens[left]) {
            power -= tokens[left];
            score += 1;
            left += 1;
            maxScore = max(maxScore, score);
        }
        // If we have score and there are at least 2 tokens left
        else if (score > 0 && left < right) {
            // Play most expensive token face-down to gain power
            power += tokens[right];
            score -= 1;
            right -= 1;
        }
        else {
            // Can't make any beneficial move
            break;
        }
    }
    
    return maxScore;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse tokens array
    int tokens[100];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        tokens[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int power;
    scanf("%d", &power);
    
    int result = solution(tokens, n, power);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), then one pass with two pointers takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables and pointers

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler