Problem
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 tokeni.
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 tokeni, losingtokens[i]
power and gaining1
score.Face-down: If your current score is at least
1
, you may play tokeni, gainingtokens[i]
power and losing1
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 to100
and increasing score to1
.Play token3 (
400
) face-down, increasing power to500
and reducing score to0
.Play token1 (
200
) face-up, reducing power to300
and increasing score to1
.Play token2 (
300
) face-up, reducing power to0
and increasing score to2
.
The maximum score achievable is 2.
Constraints:
0 <= tokens.length <= 1000
0 <= tokens[i], power < 104
Solution
/**
* @param {number[]} tokens
* @param {number} power
* @return {number}
*/
var bagOfTokensScore = function(tokens, power) {
tokens.sort((a, b) => a - b);
var left = 0;
var right = tokens.length - 1;
var maxScore = 0;
var score = 0;
while (left <= right) {
if (power >= tokens[left]) {
power -= tokens[left++];
score += 1;
maxScore = Math.max(maxScore, score);
} else if (score > 0) {
score -= 1;
power += tokens[right--];
} else {
break;
}
}
return maxScore;
};
Explain:
nope.
Complexity:
- Time complexity : O(n * log(n)).
- Space complexity : O(1).