948. Bag of Tokens

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, 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⁴

Solutions

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.

Therefore, we can sort the tokens by the amount of energy they consume, and then use two pointers: one moving from left to right and the other from right to left. In each iteration, we try to consume energy to gain points as much as possible, and then update the maximum score. If the current energy is not enough to consume the current token, we try to consume the current token using points. If the points are not enough to consume the current token, we stop the iteration.

The time complexity is $O(n \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the number of tokens.

Python3JavaC++GoTypeScript

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

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int ans = 0, score = 0;
        for (int i = 0, j = tokens.length - 1; i <= j;) {
            if (power >= tokens[i]) {
                power -= tokens[i++];
                ans = Math.max(ans, ++score);
            } else if (score > 0) {
                power += tokens[j--];
                --score;
            } else {
                break;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        int ans = 0, score = 0;
        for (int i = 0, j = tokens.size() - 1; i <= j;) {
            if (power >= tokens[i]) {
                power -= tokens[i++];
                ans = max(ans, ++score);
            } else if (score > 0) {
                power += tokens[j--];
                --score;
            } else {
                break;
            }
        }
        return ans;
    }
};

func bagOfTokensScore(tokens []int, power int) (ans int) {
    sort.Ints(tokens)
    i, j := 0, len(tokens)-1
    score := 0
    for i <= j {
        if power >= tokens[i] {
            power -= tokens[i]
            i++
            score++
            ans = max(ans, score)
        } else if score > 0 {
            power += tokens[j]
            j--
            score--
        } else {
            break
        }
    }
    return
}

function bagOfTokensScore(tokens: number[], power: number): number {
    tokens.sort((a, b) => a - b);
    let [i, j] = [0, tokens.length - 1];
    let [ans, score] = [0, 0];
    while (i <= j) {
        if (power >= tokens[i]) {
            power -= tokens[i++];
            ans = Math.max(ans, ++score);
        } else if (score) {
            power += tokens[j--];
            score--;
        } else {
            break;
        }
    }
    return ans;
}

948. Bag of Tokens

Description

Solutions

Solution 1: Greedy + Sorting + Two Pointers

Comments