Problem

You have an initial power of power, an initial score of 0, and a bag of tokens where tokens[i] is the value of the ith token (0-indexed).

Your goal is to maximize your total score by potentially playing each token in one of two ways:

  • If your current power is at least tokens[i], you may play the ith token face up, losing tokens[i] power and gaining 1 score.
  • If your current score is at least 1, you may play the ith token face down, gaining tokens[i] power and losing 1 score.

Each token may be played at most once and in any order. You do not have to play all the tokens.

Return the largest possible score you can achieve after playing any number of tokens.

Examples

Example 1:

1
2
3

Input: tokens = [100], power = 50
Output: 0
Explanation: Playing the only token in the bag is impossible because you either have too little power or too little score.

Example 2:

1
2
3
4

Input: tokens = [100,200], power = 150
Output: 1
Explanation: Play the 0th token (100) face up, your power becomes 50 and score becomes 1.
There is no need to play the 1st token since you cannot play it face up to add to your score.

Example 3:

1
2
3
4
5
6
7

Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
1. Play the 0th token (100) face up, your power becomes 100 and score becomes 1.
2. Play the 3rd token (400) face down, your power becomes 500 and score becomes 0.
3. Play the 1st token (200) face up, your power becomes 300 and score becomes 1.
4. Play the 2nd token (300) face up, your power becomes 0 and score becomes 2.

Solution

Method 1 – Two Pointers Greedy

Intuition

The key idea is to maximize score by always playing the smallest token face up when possible (to gain score cheaply), and if stuck, play the largest token face down (to regain power by sacrificing score). This greedy approach ensures we use our resources optimally.

Approach

  1. Sort the tokens in ascending order.
  2. Use two pointers: l (left) at the start and r (right) at the end of the sorted array.
  3. Initialize ans (max score), score (current score), and p (current power).
  4. While l <= r:
  • If p >= tokens[l], play token at l face up: subtract its value from p, increment score, move l right.
  • Else if score > 0, play token at r face down: add its value to p, decrement score, move r left.
  • Else, break (no moves possible).
  • Update ans with the maximum of current ans and score.
  1. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
   def bagOfTokensScore(self, tokens: list[int], power: int) -> int:
      tokens.sort()
      l, r = 0, len(tokens) - 1
      ans = score = 0
      p = power
      while l <= r:
        if p >= tokens[l]:
           p -= tokens[l]
           score += 1
           l += 1
           ans = max(ans, score)
        elif score > 0:
           p += tokens[r]
           score -= 1
           r -= 1
        else:
           break
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
   public int bagOfTokensScore(int[] tokens, int power) {
      Arrays.sort(tokens);
      int l = 0, r = tokens.length - 1;
      int ans = 0, score = 0, p = power;
      while (l <= r) {
        if (p >= tokens[l]) {
           p -= tokens[l++];
           score++;
           ans = Math.max(ans, score);
        } else if (score > 0) {
           p += tokens[r--];
           score--;
        } else {
           break;
        }
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
   int bagOfTokensScore(vector<int>& tokens, int power) {
      sort(tokens.begin(), tokens.end());
      int l = 0, r = tokens.size() - 1;
      int ans = 0, score = 0, p = power;
      while (l <= r) {
        if (p >= tokens[l]) {
           p -= tokens[l++];
           score++;
           ans = max(ans, score);
        } else if (score > 0) {
           p += tokens[r--];
           score--;
        } else {
           break;
        }
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func bagOfTokensScore(tokens []int, power int) int {
   sort.Ints(tokens)
   l, r := 0, len(tokens)-1
   ans, score, p := 0, 0, power
   for l <= r {
      if p >= tokens[l] {
        p -= tokens[l]
        score++
        l++
        if score > ans {
           ans = score
        }
      } else if score > 0 {
        p += tokens[r]
        score--
        r--
      } else {
        break
      }
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
   fun bagOfTokensScore(tokens: IntArray, power: Int): Int {
      tokens.sort()
      var l = 0
      var r = tokens.size - 1
      var ans = 0
      var score = 0
      var p = power
      while (l <= r) {
        if (p >= tokens[l]) {
           p -= tokens[l++]
           score++
           ans = maxOf(ans, score)
        } else if (score > 0) {
           p += tokens[r--]
           score--
        } else {
           break
        }
      }
      return ans
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
   pub fn bag_of_tokens_score(mut tokens: Vec<i32>, power: i32) -> i32 {
      tokens.sort();
      let (mut l, mut r) = (0, tokens.len().wrapping_sub(1));
      let (mut ans, mut score, mut p) = (0, 0, power);
      while l <= r {
        if p >= tokens[l] {
           p -= tokens[l];
           score += 1;
           l += 1;
           ans = ans.max(score);
        } else if score > 0 {
           p += tokens[r];
           score -= 1;
           if r == 0 { break; }
           r -= 1;
        } else {
           break;
        }
      }
      ans
   }
}

Complexity

  • Time: O(n log n) (for sorting, n = number of tokens)
  • Space: O(1) (in-place, ignoring sort stack)