948. Bag of Tokens

MediumGreedyArrayTwo PointersSorting
Leetcode Link

Problem Description

In this problem, you are given an initial power level and a set of tokens each with a value. The goal is to maximize your score by playing these tokens. You can play a token in one of two ways: if you have enough power, you can play it face up, consume power equal to the token's value, and increase your score by 1. Alternatively, if you have at least one score, you can play a token face down to gain power equal to its value, but you will lose one score in the process. You don't have to play all tokens, but you can only play each token once. The challenge is to decide the best strategy to play the tokens to get the highest possible score.

Intuition

The solution leverages a greedy approach. To maximize the score, the strategy is to increase the score when possible by playing the lowest value tokens face up, as this costs less power per score point gained. Conversely, when lacking power, but having at least one score, it's best to play the highest value tokens face down to gain the most power and enable more plays.

  1. Sorting the Tokens: Begin by sorting the tokens in ascending order. This allows us to play the tokens with the lowest values first to maximize score efficiently.

  2. Greedy Play: Use two pointers to track the lowest and highest value tokens not yet played. Start at the beginning (lowest value) for playing face up and the end (highest value) for playing face down.

  3. Playing Tokens Face Up: While there is enough power to play the next lowest value token, do so. This increases the score and the count of tokens played.

  4. Maximizing Score: Keep track of the maximum score achieved after each play to ensure the result reflects the highest score possible throughout the game.

  5. Playing Tokens Face Down: If there isn't enough power to play the next token face up and the score is at least 1, play the highest value token face down. This sacrifices one score to potentially gain enough power to play multiple lower value tokens, thus increasing the score.

  6. Ending Conditions: If there's no power to play any token face up and no score to play a token face down, or all tokens have been played, then no further actions can be taken and the current maximum score is the result.

The overall approach is to maximize score increment opportunities while maintaining the flexibility to regain power when necessary, without wasting potential score maximization from low-value tokens.

Learn more about Greedy, Two Pointers and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The implementation follows the intuition of playing tokens in the most efficient way, using a greedy strategy. The code organizes the solution approach into a clear sequence of steps:

  1. Sort the Tokens: First, the list of tokens is sorted using Python's built-in .sort() method. This organizes the tokens so that we can access the smallest and largest values quickly.

  2. Initialize Pointers and Variables: Two pointers, i for the lowest value tokens (start of the list) and j for the highest value tokens (end of the list), are set up. They are used to select the next token to play. We also set up ans to track the maximum score attained, and t to track the current score.

  3. Main Loop: The while loop continues as long as there are tokens left to play (i <= j). Inside the loop, we have conditions to decide whether to play a token face up or face down.

  4. Playing Tokens Face Up: If the current power is sufficient to play the next lowest value token (power >= tokens[i]), the power is reduced by the value of the token, the score counter t is incremented, and the lowest token pointer i is moved up. The optimal score ans is updated to the maximum of its current value and the new score t.

  5. Playing Tokens Face Down: If there's not enough power to play the next token face up, but we have at least one score (t), then we play the highest value token face down (power += tokens[j]), gain power equivalent to that token's value, and decrease the token and score counters (j and t).

  6. Insufficient Resources: If we have insufficient power to play a token face up and no score to play a token face down, the loop breaks as no further plays are possible.

  7. Result: Once the loop finishes, the maximum score ans is returned.

By using sorting and a greedy strategy, the algorithm ensures that we play tokens in a way that is most beneficial at each step, guaranteeing the maximum score possible with the given initial power and set of tokens.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's say our initial power level is 20, and we have a set of tokens with the following values: [4, 2, 10, 8].

  1. Sort the Tokens: We sort the tokens to get [2, 4, 8, 10].

  2. Initialize Pointers and Variables: We set i = 0, j = 3 (since there are 4 tokens, and indexes start at 0), ans = 0 for the maximum score, and t = 0 for the current score.

  3. Main Loop:

    • With 20 power, we start the loop. i = 0, j = 3.

  4. Playing Tokens Face Up:

    • We have enough power for the token at i = 0 (value = 2). We play this token face up.
    • Power is now 18 (20 - 2), t = 1, and i = 1. ans is updated to 1 since it's the maximum score till now.
    • Next, token at i = 1 (value = 4). Play it face up.
    • Power is now 14 (18 - 4), t = 2, and i = 2. Update ans to 2.
    • Now, token at i = 2 (value = 8). Play it face up.
    • Power is now 6 (14 - 8), t = 3, and i = 3. Update ans to 3.

  5. Insufficient Power to Play Face Up:

    • Token at i = 3 is worth 10, but power is only 6, so we can't play it face up.

  6. Playing Tokens Face Down:

    • We have a score (t >= 1), so we can sacrifice one score to regain power.
    • Play token at j = 3 face down. Gain 10 power.
    • Power is now 16 (6 + 10), t = 2 (as we lose one score), and j = 2 (since token at j = 3 has been played).
    • Now, we have enough power to play the token at i = 3 which is still at value 10.
    • Play it face up. Power is now 6 (16 - 10), t = 3, and i moves beyond j, meaning we've played all tokens we can play face up.
    • Update ans to 3 (it still remains the maximum score).

  7. Result:

    • We have played all the tokens we could with the power we had, maximizing the score.
    • The resulting maximum score ans is 3.

This walkthrough demonstrates the implementation of the solution approach using a simple example. The player expertly navigates through the tokens, deciding when to increase the score and when to regain power, ultimately achieving the highest score possible given the initial conditions.

Solution Implementation

1from typing import List
2
3class Solution:
4    def bag_of_tokens_score(self, tokens: List[int], power: int) -> int:
5        # Sort the tokens list to play them in increasing order of value.
6        tokens.sort()
7      
8        # Initialize two pointers and a current score.
9        # i is the start pointer, j is the end pointer.
10        left_index, right_index = 0, len(tokens) - 1
11        max_score = current_score = 0
12      
13        # Loop until the start pointer is less than or equal to the end pointer.
14        while left_index <= right_index:
15            # If there is enough power to play the smallest token.
16            if power >= tokens[left_index]:
17                # Spend power to gain a score.
18                power -= tokens[left_index]
19                left_index += 1
20                current_score += 1
21                # Update max_score to be the highest score achieved so far.
22                max_score = max(max_score, current_score)
23            # If not enough power and there is score to spend,
24            # then play the largest token to get more power.
25            elif current_score > 0:
26                power += tokens[right_index]
27                right_index -= 1
28                current_score -= 1
29            else:
30                # No moves left, break loop.
31                break
32              
33        # Return the maximum score achieved.
34        return max_score
35
1class Solution {
2    public int bagOfTokensScore(int[] tokens, int power) {
3        // Sort the tokens array to prioritize the lowest cost tokens first.
4        Arrays.sort(tokens);
5        // Initialize pointers for the two ends of the array.
6        int low = 0, high = tokens.length - 1;
7        // Initialize the maximum score and the current score (tokens turned into points).
8        int maxScore = 0, currentScore = 0;
9      
10        // Continue as long as the low pointer does not cross the high pointer.
11        while (low <= high) {
12            // If we have enough power to buy the next cheapest token, do it.
13            if (power >= tokens[low]) {
14                power -= tokens[low++]; // Buy the token and increase the low pointer.
15                currentScore++; // Increase the score by 1 for each token bought.
16                // Update the max score if the current score is greater.
17                maxScore = Math.max(maxScore, currentScore);
18            }
19            // If the power is not enough to buy, but we have some score (points),
20            // we can sell the most expensive token.
21            else if (currentScore > 0) {
22                power += tokens[high--]; // Sell the token and decrease the high pointer.
23                currentScore--; // Decrease the score by 1 for each token sold.
24            }
25            // If it's not possible to do either, exit the loop.
26            else {
27                break;
28            }
29        }
30        // Return the maximum score achieved.
31        return maxScore;
32    }
33}
34
1class Solution {
2public:
3    // This function calculates the maximum score we can achieve by playing tokens.
4    // 'tokens' is a list of token values and 'power' is the initial power.
5    int bagOfTokensScore(vector<int>& tokens, int power) {
6        // Sort the tokens to facilitate the playing strategy.
7        sort(tokens.begin(), tokens.end());
8      
9        // Initialize left and right pointers for the tokens array.
10        int left = 0;
11        int right = tokens.size() - 1;
12      
13        // 'maxScore' will hold the maximum score we can achieve.
14        // 'currentScore' will keep track of the current score while playing.
15        int maxScore = 0;
16        int currentScore = 0;
17      
18        // Play until either end of the token array is reached.
19        while (left <= right) {
20            // If we have enough power to play the smallest token, play it to gain score.
21            if (power >= tokens[left]) {
22                power -= tokens[left++];  // Reduce power by the value of the played token.
23                currentScore++;           // Increase the score as we've played a token.
24                maxScore = max(maxScore, currentScore);  // Update maxScore if it's less than currentScore.
25            // If we don't have enough power but have some score, we can trade the largest token for power.
26            } else if (currentScore > 0) {
27                power += tokens[right--]; // Increase power by the value of the traded token.
28                currentScore--;           // Decrease the score as we've traded a token for power.
29            // If we neither have the power to play nor score to trade, we cannot proceed further.
30            } else {
31                break;
32            }
33        }
34      
35        // Return the maximum score achieved.
36        return maxScore;
37    }
38};
39
1// Importing the sort function to be able to sort an array
2import { sort } from 'some-sorting-package';
3
4// The function calculates the maximum score achievable by playing tokens.
5// tokens: an array of token values; power: the initial power.
6function bagOfTokensScore(tokens: number[], power: number): number {
7    // Sort the tokens to facilitate the playing strategy.
8    sort(tokens);
9  
10    // Initialize left and right pointers for the tokens array.
11    let left = 0;
12    let right = tokens.length - 1;
13  
14    // maxScore will hold the maximum score we can achieve.
15    // currentScore will keep track of the current score while playing.
16    let maxScore = 0;
17    let currentScore = 0;
18  
19    // Play until either end of the token array is reached.
20    while (left <= right) {
21        // If we have enough power to play the smallest token, play it to gain a score.
22        if (power >= tokens[left]) {
23            power -= tokens[left];  // Reduce power by the value of the played token.
24            left += 1;  // Move to the next token.
25            currentScore += 1;  // Increase the score as we've played a token.
26            maxScore = Math.max(maxScore, currentScore);  // Update maxScore if it's less than currentScore.
27        } else if (currentScore > 0) {
28            // If we don't have enough power but have some score, we can trade the largest token for power.
29            power += tokens[right];  // Increase power by the value of the traded token.
30            right -= 1;  // Move past the traded token.
31            currentScore -= 1;  // Decrease the score as we've traded a token for power.
32        } else {
33            // If we neither have the power to play nor score to trade, we cannot proceed further.
34            break;
35        }
36    }
37  
38    // Return the maximum score achieved.
39    return maxScore;
40}
41
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Time and Space Complexity

Time Complexity

The time complexity of this code is mainly due to the sorting operation and the while loop that iterates through the list of tokens.

  • Sorting the list of tokens takes O(n log n) time, where n is the number of tokens.
  • The while loop runs in O(n) time since each token is considered at most once when either increasing or decreasing the t (score) or power. The loop will end once we've iterated through all the tokens, or we cannot make any more moves.

Hence, the overall time complexity of the code is O(n log n) due to the sorting step.

Space Complexity

The space complexity of the code is O(1). Apart from the input list, there are only a constant number of integer variables (i, j, ans, t, power) being used, regardless of the input size. Sorting is done in-place, which doesn't require extra space proportional to the input size.

Therefore, the extra space used by the program is constant, leading to a space complexity of O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ