Skip to main content
Talentd

Bag of Tokens - Solution & Explanation

MediumArrayTwo PointersGreedySorting24 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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 tokeni.

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 tokeni, losing tokens[i] power and gaining 1 score.
  • Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.

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

 

Example 1:

Input: tokens = [100], power = 50

Output: 0

Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than tokens[0] (100).

Example 2:

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

Output: 1

Explanation: Play token1 (100) face-up, reducing your power to 50 and increasing your score to 1.

There is no need to play token0, since you cannot play it face-up to add to your score. The maximum score achievable is 1.

Example 3:

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

Output: 2

Explanation: Play the tokens in this order to get a score of 2:

  1. Play token0 (100) face-up, reducing power to 100 and increasing score to 1.
  2. Play token3 (400) face-down, increasing power to 500 and reducing score to 0.
  3. Play token1 (200) face-up, reducing power to 300 and increasing score to 1.
  4. Play token2 (300) face-up, reducing power to 0 and increasing score to 2.

The maximum score achievable is 2.

 

Constraints:

  • 0 <= tokens.length <= 1000
  • 0 <= tokens[i], power < 104

Approach Overview

Problem Overview: You are given an array of token values and an initial amount of power. Each token can be played face up (spend power to gain score) or face down (spend score to gain power). The goal is to maximize the final score by choosing the right sequence of operations.

Approach 1: Greedy Two-Pointer Technique (O(n log n) time, O(1) space)

The optimal strategy comes from observing that cheap tokens are best used to gain score, while expensive tokens are best used to regain power. Start by sorting the tokens so you can process them from smallest to largest. Use two pointers: left at the smallest token and right at the largest token. If you have enough power, play the left token face up to increase score and move the pointer forward. If you lack power but have at least one score, play the right token face down to regain power and move the pointer backward. Continue until neither move is possible. This greedy decision works because spending the least power for score and reclaiming the most power when necessary keeps future options open. The sort step dominates the complexity at O(n log n), while the two-pointer scan is linear.

This approach combines ideas from Greedy, Two Pointers, and Sorting. The array structure makes operations straightforward since you only move pointers inward without modifying token values.

Approach 2: Dynamic Programming Approach (O(n^2) time, O(n^2) space)

A dynamic programming formulation explores all choices of playing tokens face up or face down while tracking current power and score. After sorting tokens, define a state based on the range of tokens already used and the current score. Transitions simulate either spending power for score or sacrificing score to gain power from a larger token. This captures every valid sequence of operations and guarantees correctness.

However, the state space grows quickly because power changes after every operation. Managing states often requires a 2D table or memoization over token ranges, leading to O(n^2) time and space complexity. The DP approach mainly serves as a conceptual baseline that proves the greedy strategy is safe. In practice, it is slower and harder to implement.

The problem heavily relies on understanding how resource trade-offs behave in a sorted Array. Once tokens are ordered, the smallest token always provides the cheapest score increase and the largest token always yields the biggest power recovery.

Recommended for interviews: The greedy two-pointer solution is what interviewers expect. It shows you recognize the structure created by sorting and can reason about optimal local decisions. Mentioning the DP idea demonstrates deeper understanding, but implementing the O(n log n) greedy approach proves strong problem-solving and optimization skills.

Approach 1: Greedy Two-Pointer Technique

This approach involves using a two-pointer technique to process the tokens. By sorting the tokens array, we aim to utilize the smallest possible tokens first to maximize score when power allows, and then balance power by utilizing score if achievable.

Start by sorting the tokens array. Maintain two pointers: one at the start to play face-up when you have enough power, and the other at the end to play face-down when a score can be sacrificed to gain more power. Keep track of the current score and maximum score achieved. This greedy approach helps in maximizing score by trying to play as many tokens face-up as possible while being able to trade score for power when needed.

The implementation begins by sorting the tokens array using qsort. Two pointers, left and right, are initialized to keep track of which tokens to consider for playing face-up or face-down. If the power is enough to play the token at the left pointer face-up, the player does so and increments the score. Otherwise, if the score allows it, the player can play the token at the right pointer face-down to increase power. The loop continues until no more moves are possible. The maximum score obtained is returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n log n) due to sorting the tokens array. The space complexity is O(1) as no additional space besides variables is used.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

In the dynamic programming approach, we consider decisions at each token in terms of playing face-up or face-down, and store results for subproblems to optimize the score obtained.

The dynamic programming table, dp[i][j], keeps track of the maximum score achievable with the first i tokens and with j power. For each token, either spend or gain power while adjusting the score, and calculate the best possible outcome for each state.

This C implementation uses a DP table to track the best scores possible at each state. As the array updates for each token processed, it compares the outcomes of playing the token face-up or face-down. The final answer is at dp[tokensSize][power], representing the maximum score achievable for the given number of tokens and initial power.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n * m) where n is the number of tokens and m is the initial power range explored. The space complexity is also O(n * m) due to the DP table usage.

Try this approach in the editor →

Approach 3: Greedy + Sorting + Two Pointers

There are two ways to use tokens: one is to consume energy to gain points, and the other is to consume points to gain energy. Obviously, we should consume as little energy as possible to gain as many points as possible.

Therefore, we can sort the tokens by the amount of energy they consume, and then use two pointers: one moving from left to right and the other from right to left. In each iteration, we try to consume energy to gain points as much as possible, and then update the maximum score. If the current energy is not enough to consume the current token, we try to consume the current token using points. If the points are not enough to consume the current token, we stop the iteration.

The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the number of tokens.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Two-Pointer Technique

The time complexity is O(n log n) due to sorting the tokens array. The space complexity is O(1) as no additional space besides variables is used.

Dynamic Programming Approach

The time complexity is O(n * m) where n is the number of tokens and m is the initial power range explored. The space complexity is also O(n * m) due to the DP table usage.

Greedy + Sorting + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Two-Pointer TechniqueO(n log n)O(1)Best practical solution. Sort tokens and use two pointers to maximize score efficiently.
Dynamic ProgrammingO(n^2)O(n^2)Useful for understanding state transitions and exploring all choices, but slower and rarely needed in practice.

Video Solution

Bag of Tokens | Greedy Explanation | Google | Leetcode 948 • codestorywithMIK • 47,739 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Bag of Tokens easy or hard?
Bag of Tokens is considered a medium difficulty problem. The implementation is short, but the challenge is recognizing the greedy pattern after sorting and managing the two-pointer decisions correctly.
How to solve Bag of Tokens in O(n)?
A strict O(n) solution is not generally possible because token values must be ordered to make the greedy decisions correctly. Sorting ensures you always spend the least power to gain score and reclaim the most power when needed. The resulting optimal algorithm is O(n log n) time with a linear two-pointer pass.
What is the best approach for Bag of Tokens?
The best approach is a greedy two-pointer strategy. First sort the tokens, then use one pointer for the smallest token and another for the largest. Spend power on the smallest token to gain score, and when power is insufficient but score is available, use the largest token to regain power. This method runs in O(n log n) time due to sorting and O(1) extra space.
What data structure is used in Bag of Tokens?
The core data structure is a sorted array of token values. After sorting, two pointers track the smallest and largest remaining tokens. This enables efficient greedy decisions without additional data structures.
What is the time complexity of Bag of Tokens?
The optimal solution runs in O(n log n) time because the tokens must be sorted first. After sorting, a two-pointer scan processes each token at most once, which takes O(n). Space complexity is O(1) if sorting is done in place.
Bag of Tokens Python or Java solution approach?
Both Python and Java implementations follow the same steps: sort the tokens, maintain two pointers, and track current power and score. When power allows, consume the smallest token to gain score; otherwise, trade a score for power using the largest token. The logic runs in O(n log n) time and constant extra space.
Is Bag of Tokens asked at Google, Amazon, or Meta?
Bag of Tokens is a common medium-level greedy problem frequently used in technical interview preparation. Variants of resource trade-off and greedy ordering appear in interviews at companies like Amazon, Google, and Meta, especially when evaluating algorithmic reasoning with sorting and pointer techniques.

Ready to solve this problem?

Practice Bag of Tokens with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays