Problem- Bag of Tokens
Leetcode Problem number 948
Bag of Tokens is an important question based on sorting and two-pointer concepts. This is the most commonly asked question in coding interviews.
Let us understand the Bag of Tokens Problem
We have given a Power 'P' and a bag of tokens in the form of an Array. we have to maximize our score by utilizing these powers.
Rules for Bag of Tokens Problem
- If Your current Power is greater than Token[i], you can increase your score by losing power equivalent to Power-Token[i].
- If Your score is greater than '1', you can either play face up or face down.
1. What is Face Up in Bag of Tokens Problem
Face Up means increase the Score by 1 and decrease power by Token[i].
2. What is Face Down in Bag of Tokens Problem
Face Down means decrease score by 1 and increase power by Token[i], where i is an index of Token array.
Lebel: Medium
Let us see some examples based on Input-Output of Bag of Tokens Problem
Example 1:
Input = [100,900,300,400,1200]
Power = 200
Output : 2
Example 2:
Input = [100,120]
Power = 10
Output : 0
Steps to Solve Bag of Tokens Problem
- Sort the Given array in Ascending Order
- Initialize to Pointer variable one from initial and other from last of the array.
- Iterate Through the array and perform your logic.
Solution for Bag of Tokens Problem
Solution in Java
class Solution {
public int bagOfTokensScore(int[] tokens, int power) {
Arrays.sort(tokens);
int i=0;
int j=tokens.length-1;
int points=0;
int res=0;
while(i<=j)
{
if(power>=tokens[i])
{
power-=tokens[i++];
res=Math.max(res,++points);
}
else if(points>0)
{
points--;
power+=tokens[j--];
}
else
{
break;
}
}
return res;
}
}
Solution of Bag of Tokens Problem in C++
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int power) {
sort(tokens.begin(),tokens.end());
int i=0,j,score=0,res=0;
j=tokens.size()-1;
while(i<=j)
{
if(power>=tokens[i])
{
score++;
power-=tokens[i];
i++;
}
else if(score>0)
{
score--;
power+=tokens[j];
j--;
}
else
{
break;
}
res=max(res,score);
}
return res;
}
};
Solution of Bag of Tokens Problem In Python
class Solution:
def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
tokens.sort()
L, H = 0, len(tokens)-1
score, res = 0, 0
while L <= H:
if tokens[L] <= P:
P-=tokens[L]
score+=1
res = max(score, res)
L+=1
elif score >= 1:
P+=tokens[H]
score-=1
H-=1
else:
break
return res
Practice This question on Leetcode - Bag of Tokens Problem
There can be another approach also to solve this problem such as the greedy approach or by using Queue. I have solved using Two pointer algorithm so that you can understand the basic approach of this problem.