#948

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Bag of Tokens

Maximize your score in the Bag of Tokens problem by strategically playing tokens with two-pointer scanning and greedy techniques.

array two pointers greedy sorting

Problem Statement

In the Bag of Tokens problem, you begin with an initial power and score of 0, along with a bag of tokens represented as an array of integers. Each token has a value, and you must strategically decide how to play the tokens to maximize your score. The two types of actions available are playing a token face-up, which decreases your power by the token's value, or playing a token face-down, which increases your score by 1 but does not affect your power.

The goal is to maximize your score by playing any number of tokens. The constraints of the problem require careful management of your power, especially when dealing with higher-value tokens. Sorting the tokens allows for an efficient decision-making process, and using two-pointer scanning with invariant tracking helps ensure the best sequence of moves.

Examples

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 details omitted.

Example 2

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

Output: 1

Play token 1 ( 100 ) face-up, reducing your power to 50 and increasing your score to 1 . There is no need to play token 0 , 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

Play the tokens in this order to get a score of 2 : The maximum score achievable is 2 .

Constraints

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

Solution Approach

Sort the Tokens

Begin by sorting the tokens array in ascending order. This allows for easier management of lower-value tokens and ensures that you can efficiently play tokens that are less expensive to face-up first, optimizing your available power.

Two-Pointer Scanning

Use two pointers: one starting at the beginning (lowest token value) and one at the end (highest token value). Try to play face-up as many tokens as possible with the available power, and when power is insufficient, play face-down to increase the score.

Greedy Strategy

The greedy strategy prioritizes playing tokens face-up when possible to conserve power and playing face-down only when no other moves are available. This ensures the score is maximized by efficiently using the available power.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(n)

The time complexity of the solution is O(n log n) due to the sorting step, where n is the length of the tokens array. The space complexity is O(n) due to the storage of the tokens array.

What Interviewers Usually Probe

Candidate uses a two-pointer approach with the correct greedy strategy.
Candidate efficiently handles edge cases, such as no tokens or very low power.
Candidate can explain how the sorting step simplifies the problem and ensures optimal performance.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly manage the two-pointer approach, leading to inefficient use of power.
Not handling edge cases like an empty token array or insufficient power correctly.
Incorrectly prioritizing tokens without considering the optimal sequence, which could result in a lower score.

Follow-up variants

Allowing the playing of tokens multiple times, either face-up or face-down, with adjusted rules.
Limiting the number of tokens that can be played face-up or face-down, adding another layer of strategy.
Adding power regeneration or token costs that affect the ability to play tokens, altering the dynamics of the problem.

FAQ

How does the greedy strategy apply to the Bag of Tokens problem?

The greedy strategy in the Bag of Tokens problem involves always playing the lowest value tokens face-up to conserve power and maximizing the score by playing tokens face-down when necessary.

What is the best way to maximize the score in the Bag of Tokens problem?

The best way to maximize the score is by sorting the tokens and using a two-pointer approach to play face-up tokens with available power, then using face-down tokens when power is insufficient.

What is the time complexity of the solution for Bag of Tokens?

The time complexity is O(n log n) due to the sorting of tokens, where n is the number of tokens.

How does the two-pointer scanning technique work in this problem?

The two-pointer technique involves using one pointer at the start of the tokens array and the other at the end. You try to play the lowest value tokens first and use higher value tokens when necessary.

Can you explain how to handle edge cases in the Bag of Tokens problem?

Edge cases such as an empty token array or insufficient power are handled by ensuring that no action is taken unless a valid move is possible, and by carefully tracking the available power during each move.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()
        ans = score = 0
        i, j = 0, len(tokens) - 1
        while i <= j:
            if power >= tokens[i]:
                power -= tokens[i]
                score, i = score + 1, i + 1
                ans = max(ans, score)
            elif score:
                power += tokens[j]
                score, j = score - 1, j - 1
            else:
                break
        return ans

Continue Practicing

#969 pancake sorting #881 boats to save people #870 advantage shuffle