Bag of Tokens

Medium

Asked by:

+4

34 views

Topics:

ArraysTwo PointersGreedy Algorithms

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.

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 token₁ (100) face-up, reducing your power to 50 and increasing your score to 1.

There is no need to play token₀, 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:

Play token₀ (100) face-up, reducing power to 100 and increasing score to 1.
Play token₃ (400) face-down, increasing power to 500 and reducing score to 0.
Play token₁ (200) face-up, reducing power to 300 and increasing score to 1.
Play token₂ (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 < 10⁴

Bag of Tokens

Medium

Asked by:

34 views

Topics:

ArraysTwo PointersGreedy Algorithms

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.

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 token₁ (100) face-up, reducing your power to 50 and increasing your score to 1.

There is no need to play token₀, 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:

Play token₀ (100) face-up, reducing power to 100 and increasing score to 1.
Play token₃ (400) face-down, increasing power to 500 and reducing score to 0.
Play token₁ (200) face-up, reducing power to 300 and increasing score to 1.
Play token₂ (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 < 10⁴

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the tokens array and the range of values within it? What is the range of the initial power?
Can the token values be negative or zero?
If it's impossible to gain any points (even starting with 0 points), what should I return? Should I return 0?
Is there any specific order in which I should prioritize playing tokens face up versus face down if both are possible at any given step?
Are there any constraints that would limit the number of tokens or the initial power such that an integer overflow could be a concern while calculating power changes?

Brute Force Solution

Approach

The brute force approach to the 'Bag of Tokens' problem means trying out every possible sequence of actions with the tokens. We essentially explore every possible order of playing tokens face-up or face-down. We aim to find the highest possible score we can achieve.

Here's how the algorithm would work step-by-step:

Consider all the ways you can choose a token to play face-up (gain score, lose power) or face-down (lose score, gain power).
For each of these choices, track the score and power you currently have.
Continue making choices until you've either used all the tokens or you can't make any more valid moves (not enough power to play face-up, or score is zero and can't play face-down).
Repeat this process for every possible starting token and every possible subsequent action.
Keep track of the highest score you achieved across all the different sequences of actions.
After exploring every possibility, the highest score you kept track of is the answer.

Code Implementation

def bag_of_tokens_brute_force(tokens, power):
    maximum_score = 0

    def solve(current_power, current_score, remaining_tokens, current_score_list):
        nonlocal maximum_score
        maximum_score = max(maximum_score, current_score)

        if not remaining_tokens:
            return

        for index in range(len(remaining_tokens)):
            
            token_value = remaining_tokens[index]
            new_remaining_tokens = remaining_tokens[:index] + remaining_tokens[index+1:]

            # Try playing the token face-up (lose power, gain score)
            if current_power >= token_value:
                solve(current_power - token_value, current_score + 1, new_remaining_tokens, current_score_list + [current_score + 1])

            # Try playing the token face-down (lose score, gain power)
            if current_score > 0:
                # Explore playing the token face down
                solve(current_power + token_value, current_score - 1, new_remaining_tokens, current_score_list + [current_score - 1])

    # We explore every possible starting state.
    solve(power, 0, tokens, [0])

    return maximum_score

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible sequences of playing tokens, where at each step we can either play a token face-up or face-down. With 'n' tokens, there are 2 possible actions (face-up or face-down) for each token, leading to 2 * 2 * ... * 2 (n times) possible sequences to explore. Therefore, the total number of possible sequences is 2^n. This exponential growth makes the time complexity O(2^n).

Space Complexity

O(N!) – The brute force approach explores every possible sequence of token actions. Each sequence can be represented as a permutation of the tokens. The recursion depth can reach N, where N is the number of tokens. At each level of recursion, we are potentially storing the current score, power, and remaining tokens (or indices of used tokens). Considering the branching factor at each level and the need to explore all permutations of token plays (face-up or face-down), the space usage grows factorially with N due to the recursive call stack and storing intermediate states for each explored path, effectively storing a path of length N!. Therefore, the auxiliary space complexity is O(N!).

Optimal Solution

Approach

The key is to maximize your score by strategically playing the tokens. We want to use the smallest tokens to gain power and the largest tokens to gain points.

Here's how the algorithm would work step-by-step:

First, arrange the tokens from smallest to largest.
While you still have tokens to play, try to gain power first. If the smallest token's value is less than or equal to your current power, play it to increase your score and reduce your power.
If you can't gain power (the smallest token is too big), and you have points and at least one token left, use your points to buy power by playing the largest remaining token. This reduces your score and increases your power. Stop if there is only one token left or you don't have any score to convert.
Repeat the process until you can no longer play any tokens.

Code Implementation

def bag_of_tokens_score(tokens, power):
    tokens.sort()
    left_pointer = 0
    right_pointer = len(tokens) - 1
    current_score = 0
    maximum_score = 0

    while left_pointer <= right_pointer:
        # Try to increase score if possible
        if power >= tokens[left_pointer]:
            power -= tokens[left_pointer]

            current_score += 1
            left_pointer += 1
            maximum_score = max(maximum_score, current_score)
        # If can't increase score and have score, then use score to increase power
        elif current_score > 0:
            # Need score to buy power
            if left_pointer < right_pointer:
                power += tokens[right_pointer]
                current_score -= 1
                right_pointer -= 1
            #if left and right are the same index, it means it is the last token
            else:
                break
        else:
            #No more moves possible
            break

    return maximum_score

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant factor in the time complexity is the initial sorting of the tokens array, which takes O(n log n) time. The while loop iterates at most n times (where n is the number of tokens), as each iteration either consumes a token from the left or the right. Within the while loop, the operations are constant time (comparison and assignment). Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The algorithm sorts the input tokens in place. Beyond that, it uses a constant amount of extra space to store variables such as the current power, score, and indices for traversing the sorted tokens. The space used by these variables does not depend on the input size N (the number of tokens). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty tokens array	Return 0 immediately as there are no tokens to play.
Null tokens array	Throw an IllegalArgumentException or return 0, depending on requirements, to handle null input.
Single token in the array, initial power is sufficient	Return 1, as we can play the single token face up to gain one point.
Single token in the array, initial power is insufficient, no points to spend	Return 0 as the token cannot be played in any configuration.
Single token in the array, initial power is insufficient, but we have one point to spend.	Return 0 as the token can be flipped for the power but the point must already be present.
All tokens have the same value, and power is less than the token value, and no points to spend	Return 0, as playing any token is impossible without points.
All tokens have the same value, and power is less than the token value, but we have points to spend	Check that points are being spent correctly and not resulting in negative points.
Tokens array contains very large integer values that could lead to integer overflow during power calculation	Use a data type with sufficient range (e.g., long) or check for potential overflows during power updates.