We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Bag of Tokens

Number: 985

Difficulty: Medium

Paid? No

Companies: Apple, Adobe, Google

Problem Description

You are given an array of tokens and an initial power. By playing tokens face-up (if you have enough power) you can gain a score, or playing them face-down (if you have a score) you can regain some power. The goal is to maximize your score by choosing the optimal order to play these tokens.

Key Insights

  • Sort the tokens to easily access the smallest and largest values.
  • Use a two-pointer approach: one pointer starts at the beginning (small tokens for gaining score) and one at the end (large tokens for regaining power).
  • Gain score by playing a low-value token (if enough power), and if you get stuck, use a high-value token to convert a score into additional power.
  • Maintain the maximum score obtained during the process.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the tokens list. Space Complexity: O(1) if sorting is done in-place, otherwise O(n).

Solution

We can solve the problem using a greedy two-pointer strategy. First, sort the tokens so that the smallest token is at the beginning and the largest at the end. Initialize two pointers: left (to gain score) and right (to gain power by sacrificing score). Keep track of the current score and update the maximum score achieved. While there are tokens available (left pointer is less than or equal to right pointer), check if the current power is enough to play the token at the left pointer. If yes, play it face-up, increase the score, reduce the power, and move the left pointer to the right. If not and if you have at least one score, play the token at the right pointer face-down to regain power (at a cost of one score) and move the right pointer to the left. Continue until you cannot make any move, and return the maximum score recorded. The main trick is to use the largest unused token to regain power when needed and to always accumulate score when possible.

Code Solutions

# Sort tokens and initialize two pointers and score variables
def bag_of_tokens_score(tokens, power):
    # sort the tokens for the greedy approach
    tokens.sort()
    left, right = 0, len(tokens) - 1
    score, max_score = 0, 0

    # process tokens until pointers meet
    while left <= right:
        # if enough power to gain score, play token face-up
        if power >= tokens[left]:
            power -= tokens[left]  # reduce power by token value
            score += 1            # increase score
            max_score = max(max_score, score)  # update maximum score
            left += 1             # move pointer to next smallest token
        # else, if we have score to exchange for power
        elif score > 0 and left < right:
            score -= 1            # sacrifice score
            power += tokens[right] # regain power from the largest unused token
            right -= 1            # move pointer to next largest token
        else:
            # no more moves can be made
            break

    return max_score

# Example usage:
# tokens = [100, 200, 300, 400], power = 200
# Expected output: 2
print(bag_of_tokens_score([100, 200, 300, 400], 200))
← Back to All Questions