Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/948.html
948. Bag of Tokens (Medium)
You have an initial power P
, an initial score of 0
points, and a bag of tokens.
Each token can be used at most once, has a value token[i]
, and has potentially two ways to use it.
 If we have at least
token[i]
power, we may play the token face up, losingtoken[i]
power, and gaining1
point.  If we have at least
1
point, we may play the token face down, gainingtoken[i]
power, and losing1
point.
Return the largest number of points we can have after playing any number of tokens.
Example 1:
Input: tokens = [100], P = 50 Output: 0
Example 2:
Input: tokens = [100,200], P = 150 Output: 1
Example 3:
Input: tokens = [100,200,300,400], P = 200 Output: 2
Note:
tokens.length <= 1000
0 <= tokens[i] < 10000
0 <= P < 10000
Related Topics:
Greedy
Solution 1. Greedy + Two Pointers
Intuition: We would want to buy high value tokens using score and sell low value tokens to get scores.
So we should:
 sort the tokens in asending order.
 Try to use
P
to cover as much low value tokens as possible to get scores.  We buy the highest value token using one score, and add the value to
P
. If we can’t buy any token, break.  Repeat step 2 and 3 until we’ve visited all tokens.
 The final score we get is the answer.
// OJ: https://leetcode.com/problems/bagoftokens/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int P) {
sort(tokens.begin(), tokens.end());
int i = 0, j = tokens.size()  1, S = 0; // i points to the next low value token we can sell, j points to the next high value token we can buy, S is the score.
while (i <= j) {
while (i <= j && tokens[i] <= P) { // tokens[i] can be covered by `P`, sell it for score.
P = tokens[i++];
S++;
}
if (i < j && S) { // if i == j, we can't sell any token after buying this token. So we only buy this tokens[j] if i < j and we have some score left.
S;
P += tokens[j];
} else break;
}
return S;
}
};
Java

class Solution { public int bagOfTokensScore(int[] tokens, int P) { Arrays.sort(tokens); int low = 0, high = tokens.length  1; int points = 0, power = P; int maxPoints = 0; while (low <= high) { if (tokens[low] > power && points == 0) break; if (tokens[low] <= power) { power = tokens[low]; low++; points++; } else { power += tokens[high]; high; points; } maxPoints = Math.max(maxPoints, points); } return maxPoints; } }

Todo

class Solution: def bagOfTokensScore(self, tokens: List[int], power: int) > int: tokens.sort() i, j = 0, len(tokens)  1 ans = t = 0 while i <= j: if power >= tokens[i]: power = tokens[i] i, t = i + 1, t + 1 ans = max(ans, t) elif t: power += tokens[j] j, t = j  1, t  1 else: break return ans ############ class Solution(object): def bagOfTokensScore(self, tokens, P): """ :type tokens: List[int] :type P: int :rtype: int """ print(tokens) tokens.sort() N = len(tokens) left, right = 0, N  1 points = 0 remain = N while left < N and P >= tokens[left]: P = tokens[left] points += 1 left += 1 remain = 1 if left == 0 or left == N: return points while points > 0 and remain > 1: P += tokens[right] right = 1 points = 1 remain = 1 while left <= right and P >= tokens[left]: P = tokens[left] points += 1 left += 1 remain = 1 return points