Leetcode Daily | 12–09–22 | Bag Of Tokens

Hello everyone,

So from today onwards I have decided to post this blog for the Leetcode daily challenge with its explanation from brute force to optimized one. Since many people face problems while understanding the code, I decided to give a proper explanation for every statement in the code.

Here is the question that we will be looking at today.

Question

You have an initial power of power, 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.

Constraints:

• 0 <= tokens.length <= 1000
• 0 <= tokens[i], power < 104

You can find the link to the question here, https://leetcode.com/problems/bag-of-tokens/

Approach

For the first approach, we will use two pointers and greedy method. This can only be applied to the array if it is sorted in acending order.

We will place on pointer at the staring and another one at the end. After that, we will teaversing the array till the starting pointer becomes equal to the ending pointer. While traversing, we will keep a track of elements.

If the element is greater than the power, we will look the score and gain the power. Else, if the element is less than the power, we will gain a score and loose the power.

Here is the algorithm that we will be using in this code-

1. sort the token in increasing order
2. create two pointer i, j, where i = 0, j = n ; initially
3. 0 <= x <= i represent the tokens face up i.e, [Score ⬆, Power ⬇]
4. j <= x <= n represent the tokens face down i.e, [Score ⬇, Power⬆]
5. if we have sufficient power to face up ith token, power — token[i], i++.
6. else if we have some score [i - (n - j)] face down jth token, j--, power + token[j].
   i - (n - j) represents the score since (face up - face down) = score, face up = i and face down = n - j
   Note :we also need to check if we face down j we should have some unplayed token to face up. That's why we are checking j > i + 1
7. if we have no move to make break the loop.

C++ Code

Java Code

Python Code

The time complexity of the above code is O(nlogn) and the space complexity is O(1).