DevExCode

LeetCode 948: Bag of Tokens Solution

Master LeetCode problem 948 (Bag of Tokens), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

948. Bag of Tokens

Medium
ArrayTwo PointersGreedySorting

Problem Explanation

Explanation:

To maximize the total score, we need to follow a strategy that allows us to make the most out of our available power and score. The idea is to sort the tokens array so that we can utilize the tokens with the least value first. We then try to play tokens face-up as long as our power is enough, and if not, we can play tokens face-down to gain power.

  1. Sort the tokens array.
  2. Initialize two pointers, left at the start of the array and right at the end.
  3. While left <= right:
    • If we can play the token face-up (power >= token value), we play it face-up, increase the score, and move left pointer to the right.
    • If we can't play face-up and the score is greater than 0, we play a token face-down to increase power, decrease score, and move right pointer to the left.
    • If we can't play face-up and the score is 0, we break out of the loop.

Time complexity: O(nlogn) where n is the number of tokens
Space complexity: O(1)

Solution Code

import java.util.Arrays;

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

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 948 (Bag of Tokens)?

This page provides optimized solutions for LeetCode problem 948 (Bag of Tokens) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 948 (Bag of Tokens)?

The time complexity for LeetCode 948 (Bag of Tokens) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 948 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 948 in Java, C++, or Python.

Back to LeetCode Solutions