How do you solve Bag of Tokens on LeetCode?

Bag of Tokens (LeetCode #948) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: Tokens should be sorted to maximize score efficiently.

What is the time complexity of Bag of Tokens?

The optimal solution for Bag of Tokens runs in O(n log n) time and uses O(1) space. The complexity is O(n log n) due to the sorting step, and O(1) for the space used since we only use a few variables.

What is the brute force solution for Bag of Tokens?

The brute force approach for Bag of Tokens is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach tries every possible combination of playing tokens face-up and face-down to find the maximum score. This method ensures that all possibilities are explored, but it is inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Bag of Tokens?

Bag of Tokens uses the following concepts: Array, Two Pointers, Greedy, Sorting. The recommended patterns to study are: Two Pointers, Greedy, Sorting.

What are the interview tips for Bag of Tokens?

Always consider edge cases, like when power is initially less than the smallest token. Explain your thought process clearly while coding. Practice explaining your approach to someone else to solidify your understanding.

What are common mistakes when solving Bag of Tokens?

Not sorting the tokens before processing. Failing to check if score is greater than 0 before playing face-down.

#948

Bag of Tokens

Medium

ArrayTwo PointersGreedySortingTwo PointersGreedySorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(1)

💡

Intuition

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

The optimal solution uses a two-pointer technique after sorting the tokens. This allows us to maximize the score by efficiently deciding when to play tokens face-up or face-down based on our current power and score.

⚙️

Algorithm

5 steps

1Step 1: Sort the tokens array in ascending order.
2Step 2: Initialize two pointers: one at the start (left) and one at the end (right) of the sorted array.
3Step 3: While left pointer is less than or equal to right pointer, check if power is sufficient to play the left token face-up. If yes, play it and move the left pointer right, increasing score.
4Step 4: If power is insufficient, check if score is greater than 0 to play the right token face-down. If yes, play it and move the right pointer left, decreasing score.
5Step 5: Continue until no more valid moves can be made, and return the maximum score.

solution.py21 lines

1# Full working Python code
2
3def maxScore(tokens, power):
4    tokens.sort()
5    left, right = 0, len(tokens) - 1
6    score = 0
7    max_score = 0
8
9    while left <= right:
10        if power >= tokens[left]:
11            power -= tokens[left]
12            score += 1
13            left += 1
14        elif score > 0:
15            power += tokens[right]
16            score -= 1
17            right -= 1
18        else:
19            break
20        max_score = max(max_score, score)
21    return max_score

ℹ

Complexity note: The complexity is O(n log n) due to the sorting step, and O(1) for the space used since we only use a few variables.

1Tokens should be sorted to maximize score efficiently.
2Using two pointers allows us to make optimal decisions based on current power and score.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.