948. Bag of Tokens - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - The greedy approach requires sorting tokens to access smallest and largest values efficiently
Two Pointers - Used to track the smallest (left) and largest (right) tokens simultaneously
Greedy Algorithms - Understanding when local optimal choices lead to global optimal solutions

1. Greedy + Two Pointers

Intuition

To maximize our score, we should be strategic about which tokens we play face-up (losing power, gaining score) versus face-down (gaining power, losing score). The key insight is that when gaining score, we want to spend as little power as possible, and when gaining power, we want to gain as much as possible. Sorting the tokens lets us always play the smallest token face-up and the largest token face-down.

Algorithm

Sort the tokens in ascending order.
Use two pointers: l starts at the beginning, r at the end.
While l <= r:
- If we have enough power to play tokens[l] face-up, do it (gain 1 score, lose that power). Update the maximum score seen.
- Else if we have at least 1 score, play tokens[r] face-down (lose 1 score, gain that power).
- Otherwise, we can't make any more moves, so break.
Return the maximum score achieved.

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        res = score = 0
        tokens.sort()
        l, r = 0, len(tokens) - 1
        while l <= r:
            if power >= tokens[l]:
                power -= tokens[l]
                l += 1
                score += 1
                res = max(res, score)
            elif score > 0:
                power += tokens[r]
                r -= 1
                score -= 1
            else:
                break
        return res

public class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int res = 0, score = 0, l = 0, r = tokens.length - 1;

        while (l <= r) {
            if (power >= tokens[l]) {
                power -= tokens[l++];
                score++;
                res = Math.max(res, score);
            } else if (score > 0) {
                power += tokens[r--];
                score--;
            } else {
                break;
            }
        }

        return res;
    }
}

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        int res = 0, score = 0, l = 0, r = tokens.size() - 1;

        while (l <= r) {
            if (power >= tokens[l]) {
                power -= tokens[l++];
                score++;
                res = max(res, score);
            } else if (score > 0) {
                power += tokens[r--];
                score--;
            } else {
                break;
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} tokens
     * @param {number} power
     * @return {number}
     */
    bagOfTokensScore(tokens, power) {
        tokens.sort((a, b) => a - b);
        let res = 0,
            score = 0,
            l = 0,
            r = tokens.length - 1;

        while (l <= r) {
            if (power >= tokens[l]) {
                power -= tokens[l++];
                score++;
                res = Math.max(res, score);
            } else if (score > 0) {
                power += tokens[r--];
                score--;
            } else {
                break;
            }
        }

        return res;
    }
}

public class Solution {
    public int BagOfTokensScore(int[] tokens, int power) {
        Array.Sort(tokens);
        int res = 0, score = 0, l = 0, r = tokens.Length - 1;

        while (l <= r) {
            if (power >= tokens[l]) {
                power -= tokens[l++];
                score++;
                res = Math.Max(res, score);
            } else if (score > 0) {
                power += tokens[r--];
                score--;
            } else {
                break;
            }
        }

        return res;
    }
}

func bagOfTokensScore(tokens []int, power int) int {
    sort.Ints(tokens)
    res, score, l, r := 0, 0, 0, len(tokens)-1

    for l <= r {
        if power >= tokens[l] {
            power -= tokens[l]
            l++
            score++
            if score > res {
                res = score
            }
        } else if score > 0 {
            power += tokens[r]
            r--
            score--
        } else {
            break
        }
    }

    return res
}

class Solution {
    fun bagOfTokensScore(tokens: IntArray, power: Int): Int {
        tokens.sort()
        var res = 0
        var score = 0
        var l = 0
        var r = tokens.size - 1
        var p = power

        while (l <= r) {
            if (p >= tokens[l]) {
                p -= tokens[l++]
                score++
                res = maxOf(res, score)
            } else if (score > 0) {
                p += tokens[r--]
                score--
            } else {
                break
            }
        }

        return res
    }
}

class Solution {
    func bagOfTokensScore(_ tokens: [Int], _ power: Int) -> Int {
        let tokens = tokens.sorted()
        var res = 0, score = 0, l = 0, r = tokens.count - 1
        var power = power

        while l <= r {
            if power >= tokens[l] {
                power -= tokens[l]
                l += 1
                score += 1
                res = max(res, score)
            } else if score > 0 {
                power += tokens[r]
                r -= 1
                score -= 1
            } else {
                break
            }
        }

        return res
    }
}

impl Solution {
    pub fn bag_of_tokens_score(tokens: Vec<i32>, power: i32) -> i32 {
        let mut tokens = tokens;
        tokens.sort();
        let mut res = 0;
        let mut score = 0;
        let mut l: i32 = 0;
        let mut r: i32 = tokens.len() as i32 - 1;
        let mut power = power;

        while l <= r {
            if power >= tokens[l as usize] {
                power -= tokens[l as usize];
                l += 1;
                score += 1;
                res = res.max(score);
            } else if score > 0 {
                power += tokens[r as usize];
                r -= 1;
                score -= 1;
            } else {
                break;
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

Common Pitfalls

Forgetting to Sort the Tokens

The greedy approach only works on sorted tokens. Without sorting, you cannot guarantee playing the smallest token face-up and largest face-down.

# Wrong: using unsorted tokens
l, r = 0, len(tokens) - 1
# Right: sort first
tokens.sort()
l, r = 0, len(tokens) - 1

Playing Face-Down with Zero Score

You cannot play a token face-down to gain power unless you have at least 1 score to spend. Attempting this leads to incorrect results.

# Wrong: no score check before face-down play
else:
    power += tokens[r]
    r -= 1
    score -= 1
# Right: require score > 0
elif score > 0:
    power += tokens[r]
    r -= 1
    score -= 1

Returning Current Score Instead of Maximum

The score fluctuates as you play tokens face-down. You must track the maximum score achieved, not just the final score.

# Wrong: returning final score
return score
# Right: track and return maximum
res = max(res, score)  # update after each face-up play
return res