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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Bag of Tokens

Difficulty: Medium

Problem Description

You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens. Your goal is to maximize the total score by strategically playing these tokens. You can play an unplayed token in one of two ways: face-up (if your current power is at least tokens[i], losing tokens[i] power and gaining 1 score) or face-down (if your current score is at least 1, gaining tokens[i] power and losing 1 score). Return the maximum possible score you can achieve after playing any number of tokens.

Key Insights

  • Playing tokens face-up increases the score but decreases power.
  • Playing tokens face-down increases power but decreases score.
  • The strategy involves balancing the use of tokens to maximize score while managing power effectively.
  • Sorting the tokens helps in determining the optimal order of playing them.
  • A two-pointer technique can be used to efficiently explore the possible plays of tokens.

Space and Time Complexity

Time Complexity: O(n log n) - the sorting step dominates the overall time complexity. Space Complexity: O(1) - the solution can be implemented in-place with a fixed amount of additional space.

Solution

The problem can be solved using a greedy algorithm and a two-pointer approach. First, sort the tokens in ascending order. Use two pointers: one starting from the lowest value (beginning of the list) and one from the highest value (end of the list). The strategy is to maximize the score by playing tokens face-up when possible and playing tokens face-down when necessary to regain power. The process continues until all possible moves are exhausted.

Code Solutions

def bagOfTokensScore(tokens, power):
    tokens.sort()
    score = 0
    max_score = 0
    left, right = 0, len(tokens) - 1

    while left <= right:
        if power >= tokens[left]:
            power -= tokens[left]
            score += 1
            max_score = max(max_score, score)
            left += 1
        elif score > 0:
            power += tokens[right]
            score -= 1
            right -= 1
        else:
            break
    
    return max_score
← Back to All Questions