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.
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 theith
token face up, losingtokens[i]
power and gaining1
score. - If your current score is at least
1
, you may play theith
token face down, gainingtokens[i]
power and losing1
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-
- sort the token in increasing order
- create two pointer i, j, where
i = 0, j = n
; initially 0 <= x <= i
represent the tokens face up i.e, [Score ⬆, Power ⬇]j <= x <= n
represent the tokens face down i.e, [Score ⬇, Power⬆]- if we have sufficient power to face up ith token, power — token[i], i++.
- 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
- 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).