Bag Of Tokens - Leetcode Solution

Problem Statement:

You have an initial power of P, an initial score of 0, and a bag of tokens where tokens[i] is the value of the ith token (0-indexed).

Your goal is to maximize your total score by potentially playing each token in one of two ways:

If your current power is at least tokens[i], you may play the ith token face up, losing tokens[i] power and gaining 1 score. If your current score is at least 1, you may play the ith token face down, gaining tokens[i] power and losing 1 score. Each token may be played at most once and in any order. You do not have to play all the tokens.

Return the largest possible score you can achieve after playing any number of tokens.

Example:

Input: tokens = [100,200,300,400], P = 200 Output: 2 Explanation: Play the tokens in this order:

1. Play the 0th token (100) face up, your power becomes 100 and score becomes 1.
2. Play the 3rd token (400) face down, your power becomes 500 and score becomes 0.
3. Play the 1st token (200) face up, your power becomes 300 and score becomes 1.
4. Play the 2nd token (300) face up, your power becomes 0 and score becomes 2.

Solution Approach:

In order to maximize our score in this problem, we should always pick the token which gives the highest score and then use it to either gain more score or gain more power. One optimal strategy is to always play a token with the least power face up, and always playing the token with the most power face down. If a particular token cannot be played face down because the score is currently 0, we skip that token. We can use a greedy approach by considering all the tokens in a sorted order. We first sort the tokens in ascending order and initialize two pointers ‘left’ and ‘right’, pointing to the lowest and highest token in the sorted tokens array respectively. We set the initial score to 0 and keep track of the maxScore at each iteration. We repeatedly check if the current power is greater than the value of the left token, then we add 1 to the score, subtract the power by the value of the left token, and move the ‘left’ pointer to the right by 1. And if the score is greater than 0 and the current power is less than the value of the right token, then we add the value of the right token to the power, subtract 1 from the score and move the ‘right’ pointer to the left by 1. We keep doing this until there are no moves left to make.

Pseudo Code:

1. Sort the array of tokens in ascending order.
2. Initialize the left and right pointers to the lowest and highest token value in the sorted array respectively.
3. Initialize the current power to the given value P and the current score to 0.
4. Initialize a variable maxScore to 0.
5. While the left pointer is less than or equal to the right pointer:
   1. If the current power is greater than or equal to the value of the token pointed by the left pointer, add 1 to the score, subtract the value of the token pointed by the left pointer from the current power and move the left pointer to the right by 1.
   2. Else if the score is greater than 0 and the current power is less than the value of the token pointed by the right pointer, add the value of the token pointed by the right pointer to the current power, subtract 1 from the score and move the right pointer to the left by 1.
   3. Else break from the loop.
   4. If the current score is greater than the maxScore, update maxScore to the current score.
6. Return maxScore.

Time and Space Complexity:

Sorting the array of tokens takes O(n log n) time where n is the number of tokens. The while loop takes O(n) time as the total number of iterations is at most 2n. Thus, the overall time complexity of the algorithm is O(n log n). The space complexity of the algorithm is O(1) as we are not using any additional data structure to store the information.

1