Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

948. Bag of Tokens

Time:

Space: 

			


class Solution {
 public:
  int bagOfTokensScore(vector<int>& tokens, int power) {
    int ans = 0;
    int score = 0;
    int i = 0;                  // Index of smallest token
    int j = tokens.size() - 1;  // Index of largest token

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

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




			


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




			


class Solution:
  def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
    ans = 0
    score = 0
    q = 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