Skip to content

948. Bag of Tokens 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int bagOfTokensScore(vector<int>& tokens, int power) {
    int ans = 0;
    int score = 0;
    int i = 0;                  // index of the smallest token
    int j = tokens.size() - 1;  // index of the largest token

    sort(tokens.begin(), tokens.end());

    while (i <= j && (power >= tokens[i] || score)) {
      while (i <= j && power >= tokens[i]) {
        // Play the smallest face up.
        power -= tokens[i++];
        ++score;
      }
      ans = max(ans, score);
      if (i <= j && score) {
        // Play the largest face down.
        power += tokens[j--];
        --score;
      }
    }

    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
24
25
26
class Solution {
  public int bagOfTokensScore(int[] tokens, int power) {
    int ans = 0;
    int score = 0;
    int i = 0;                 // index of the smallest token
    int j = tokens.length - 1; // index of the largest token

    Arrays.sort(tokens);

    while (i <= j && (power >= tokens[i] || score > 0)) {
      while (i <= j && power >= tokens[i]) {
        // Play the smallest face up.
        power -= tokens[i++];
        ++score;
      }
      ans = Math.max(ans, score);
      if (i <= j && score > 0) {
        // Play the largest face down.
        power += tokens[j--];
        --score;
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
    ans = 0
    score = 0
    q = collections.deque(sorted(tokens))

    while q and (power >= q[0] or score):
      while q and power >= q[0]:
        # Play the smallest face up.
        power -= q.popleft()
        score += 1
      ans = max(ans, score)
      if q and score:
        # Play the largest face down.
        power += q.pop()
        score -= 1

    return ans