Bag of Tokens - LeetCode Daily Challenge

Problem Statement

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

There is no need to play token0, 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 token0 (100) face-up, reducing power to 100 and increasing score to 1.
Play token3 (400) face-down, increasing power to 500 and reducing score to 0.
Play token1 (200) face-up, reducing power to 300 and increasing score to 1.
Play token2 (300) face-up, reducing power to 0 and increasing score to 2.
The maximum score achievable is 2.

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int low = 0, high = tokens.length - 1, score = 0;

        while(low <= high) {
            if(power >= tokens[low]) {
                score += 1;
                power -= tokens[low];
                low += 1;
            } else if(low != high && score > 0) {
                score -= 1;
                power += tokens[high];
                high -= 1;
            } else {
                return score;
            }
        }
        
        return score;
    }
}

C++ Code

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        int low = 0, high = tokens.size() - 1, score = 0;

        while (low <= high) {
            if (power >= tokens[low]) {
                ++score;
                power -= tokens[low++];
            } else if (low != high && score > 0) {
                --score;
                power += tokens[high--];
            } else {
                return score;
            }
        }
        return score;
    }
};

Python Code

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()
        low, high, score = 0, len(tokens) - 1, 0

        while low <= high:
            if power >= tokens[low]:
                score += 1
                power -= tokens[low]
                low += 1
            elif low != high and score > 0:
                score -= 1
                power += tokens[high]
                high -= 1
            else:
                return score

        return score

Javascript Code

var bagOfTokensScore = function(tokens, power) {
    tokens.sort((a, b) => a - b);
    let low = 0,
        high = tokens.length - 1,
        score = 0;

    while (low <= high) {
        if (power >= tokens[low]) {
            score++;
            power -= tokens[low++];
        } else if (low !== high && score > 0) {
            score--;
            power += tokens[high--];
        } else {
            return score;
        }
    }

    return score;
};

Go Code

func bagOfTokensScore(tokens []int, power int) int {
    sort.Ints(tokens)
    low, high, score := 0, len(tokens)-1, 0

    for low <= high {
        if power >= tokens[low] {
            score++
            power -= tokens[low]
            low++
        } else if low != high && score > 0 {
            score--
            power += tokens[high]
            high--
        } else {
            return score
        }
    }

    return score
}

Complexity Analysis

Time Complexity: O(N * logN), we are sorting the array and then iterating each element once. Hence, it would effectively be O(N * logN).
Space Complexity: O(1), we are not taking any extra space.