Bag of Tokens

medium greedy two pointers sorting

Problem

You start with an initial amount of power and a score of 0. You have a bag of tokens. You may play a token face-up (if your power is at least the token value, spend that much power to gain 1 score) or face-down (if your score is at least 1, spend 1 score to gain the token's power). Each token can be played at most once, in any order. Return the maximum score you can achieve.

Inputtokens = [100, 200, 300, 400], power = 200

Output2

Play 100 face-up (power 100, score 1), play 400 face-down (power 500, score 0), play 200 face-up (power 300, score 1), play 300 face-up (power 0, score 2).

tokens (comma-separated)

power

def bag_of_tokens_score(tokens, power):
    tokens.sort()
    lo, hi = 0, len(tokens) - 1
    score = best = 0
    while lo <= hi:
        if power >= tokens[lo]:
            power -= tokens[lo]
            lo += 1
            score += 1
            best = max(best, score)
        elif score > 0 and lo < hi:
            power += tokens[hi]
            hi -= 1
            score -= 1
        else:
            break
    return best

function bagOfTokensScore(tokens, power) {
  tokens.sort((a, b) => a - b);
  let lo = 0, hi = tokens.length - 1;
  let score = 0, best = 0;
  while (lo <= hi) {
    if (power >= tokens[lo]) {
      power -= tokens[lo++];
      score += 1;
      best = Math.max(best, score);
    } else if (score > 0 && lo < hi) {
      power += tokens[hi--];
      score -= 1;
    } else {
      break;
    }
  }
  return best;
}

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int lo = 0, hi = tokens.length - 1;
        int score = 0, best = 0;
        while (lo <= hi) {
            if (power >= tokens[lo]) {
                power -= tokens[lo++];
                score += 1;
                best = Math.max(best, score);
            } else if (score > 0 && lo < hi) {
                power += tokens[hi--];
                score -= 1;
            } else {
                break;
            }
        }
        return best;
    }
}

int bagOfTokensScore(vector<int>& tokens, int power) {
    sort(tokens.begin(), tokens.end());
    int lo = 0, hi = (int)tokens.size() - 1;
    int score = 0, best = 0;
    while (lo <= hi) {
        if (power >= tokens[lo]) {
            power -= tokens[lo++];
            score += 1;
            best = max(best, score);
        } else if (score > 0 && lo < hi) {
            power += tokens[hi--];
            score -= 1;
        } else {
            break;
        }
    }
    return best;
}

Explanation

We trade power and score back and forth, and we want the highest score ever reached. The greedy idea: when buying score with power, buy it as cheaply as possible; when buying power with score, sell that score for as much power as possible.

So we sort the tokens and use two pointers — lo at the cheapest token, hi at the most expensive. Playing the cheapest token face-up gains a point for the least power; playing the priciest token face-down gives the most power back for one point.

Each step, if we can afford tokens[lo] we play it face-up: spend that power, gain a point, advance lo, and update best. Otherwise, if we have at least one point and tokens remain, we play tokens[hi] face-down: gain its power, lose a point, retreat hi. If neither move is possible we stop.

We track best separately because the score may dip when we sacrifice a point to buy power — the answer is the maximum score seen at any moment, not the final one.

Example: tokens=[100,200,300,400], power=200. Buy 100 (power 100, score 1), buy nothing more cheaply, so sell using 400 (power 500, score 0), then buy 200 and 300 (score 2). Best score reached is 2.

Time: O(n log n) Space: O(1)