LeetCode 948: Bag of Tokens

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)

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;
    }
}