Just solved this on my own! Came to see here the solution, and we have the same solution! Wouldn't have been able to do it if someone asked me to do it 3 months ago! Practise is the key!
@@ryandixon3252not sure why you're irked by their spelling. Practice has 2 spellings depending on which version of English you use. The way they spelled it is completely fine...
I was close man...now I am at a point of LC problems where I am able to think the algorithm but cannot code it up. I guess being able to think it in 20-25 mins is still an improvement. I tracked down sorting it and also shifting the pointers.
After reading the question initially I thought it was a dp problem. I get really confused between dp and greedy. I know dp can be taken when there's choice and some optimising (like min, max) specified in the question. So I thought it to be dp...How to get intuition that a problem is greedy or dp ?
I think one way to put it is to think if there's a necessarily optimal choice (locally optimal that leads to overall optimal) that can always be made, and if so, then a greedy solution should be possible, and is probably more "correct" for the problem. The main reason for using DP, as opposed to greedy, is when locally optimal choices do not necessarily lead to the overall optimal solution. In typical examples of DP problems where you have choices (like take or leave), you don't know whether taking or leaving would lead to the overall optimal solution, because that depends on future iterations / sub-problems, and because of that, you have to use DP to exhaust all possibilities and combinations. In such problems, you would also realize that greedy could lead you down a sub-optimal path very easily since it only accounts for locally optimal solutions, so that's a clear no-no. However, in this problem, you realize after sorting that you can always make an optimal choice (locally optimal but also leads to overall optimal). After sorting, if you have enough power to face-up (gain score, lose power) a token, then it doesn't make much sense to ignore that token, since any other token you consider (after that token) will cost you more power, which already sounds quite sub-optimal (why take the more expensive and leave the cheaper). Similarly, if you have no power, then you should face-down (lose score, gain power) the token with the highest value, because the alternative of ignoring the highest value token, and going to a lesser value token, means you are going to get less power for the score you lose which again, seems quite sub-optimal, and you cannot consider face-up because you don't have enough power for the cheapest token available (remember sorted so no point looking for another token that you might be able to face-up). Really, the problem with greedy algorithms is dealing with the doubt of guaranteed optimality, since the guarantee is only available if the local optimal leads to overall optimal, and that can be challenging to get a feel for, or even prove. This is one of the examples where the overall optimal choice is a bit more obvious, and it is also the locally optimal choice. But of course, there are also plenty of problems where it's very difficult to see why greedy works (why local optimal contributes to overall optimal). By learning about the properties of DP and greedy, when each is appropriate, and by building intuition with practice, you should be able to get a slight feel for when greedy or DP is more appropriate for a problem.
You can actually stop the simulation once there is only one token left that cannot be used face up. This happens when left and right pointers meet at the same token. So if you add a conditional of left < right, you don’t need to update a res to a max score since the score variable will stop at the max and you can just break out. You do need to keep the whole loop as
anyone pls give the following approach a watch, and do let me know, why the recursive approach fails? (here, the idea is simple, incase power is atleast tokens[i], I reduce the power and increase the score, else if score>0 then I reduce the score but increase the power and else i skip. At last I return the max of the answers obtained).. class Solution { int f(vector& tokens,int p,int i,int score){ if(i==tokens.size()) return score; int faceDown=-1e9; int faceUp=-1e9; if(p>=tokens[i]){
Thank you for the explanation. I have a question regarding this problem. Initially, I attempted to solve it using dynamic programming, as we aim to maximize the score without sorting the tokens array. However, my solution was ineffective and not optimized, as it utilized a space complexity of O(n). Does dynamic programming conflict with a greedy approach in this context?
I actually solved this problem on my own. Later came to check out the video. It was almost the same code. Big thanks to neetcode sir!! Watching his videos daily is improving our problem solving skills.
Java Solution class Solution { public int bagOfTokensScore(int[] tokens, int power) { int max = 0; int i=0,j=tokens.length-1; int t = 0; Arrays.sort(tokens); while ( i
Hey love your stuff, I'm really interested in getting pro for a lifetime on your site... any idea when you would run the next promotion/discount? Would really appreciate it.
thought this was a backtracking solution, which worked for the test cases but got a time limit exceeded. Do you have any tips on how to recognize this as a two pointer vs backtracking?
What time do you upload this daily leetcode challenges? Because when I stuck and try to search your RUclips video about this problem, it's not there yet so i had to resort to the official leetcode solutions (luckily its not for premium).
For web development, I would expect more take home assignments than code interview qs like this- but easy and maybe some easisr mediums are likely typical.
Just solved this on my own! Came to see here the solution, and we have the same solution! Wouldn't have been able to do it if someone asked me to do it 3 months ago! Practise is the key!
gj bro
can do leetcode medium but cant spell practice. Forsure bro!
@@ryandixon3252not sure why you're irked by their spelling. Practice has 2 spellings depending on which version of English you use. The way they spelled it is completely fine...
Same for me. My approach is a slight variation of the one mentioned.
I was close man...now I am at a point of LC problems where I am able to think the algorithm but cannot code it up. I guess being able to think it in 20-25 mins is still an improvement. I tracked down sorting it and also shifting the pointers.
Just practice brother , I was at this stage , that you are , by time you will improve and will be able to implement your thoughts
lots of love brother! happy coding@@dingus2332
After reading the question initially I thought it was a dp problem. I get really confused between dp and greedy. I know dp can be taken when there's choice and some optimising (like min, max) specified in the question. So I thought it to be dp...How to get intuition that a problem is greedy or dp ?
I think one way to put it is to think if there's a necessarily optimal choice (locally optimal that leads to overall optimal) that can always be made, and if so, then a greedy solution should be possible, and is probably more "correct" for the problem. The main reason for using DP, as opposed to greedy, is when locally optimal choices do not necessarily lead to the overall optimal solution. In typical examples of DP problems where you have choices (like take or leave), you don't know whether taking or leaving would lead to the overall optimal solution, because that depends on future iterations / sub-problems, and because of that, you have to use DP to exhaust all possibilities and combinations. In such problems, you would also realize that greedy could lead you down a sub-optimal path very easily since it only accounts for locally optimal solutions, so that's a clear no-no. However, in this problem, you realize after sorting that you can always make an optimal choice (locally optimal but also leads to overall optimal). After sorting, if you have enough power to face-up (gain score, lose power) a token, then it doesn't make much sense to ignore that token, since any other token you consider (after that token) will cost you more power, which already sounds quite sub-optimal (why take the more expensive and leave the cheaper). Similarly, if you have no power, then you should face-down (lose score, gain power) the token with the highest value, because the alternative of ignoring the highest value token, and going to a lesser value token, means you are going to get less power for the score you lose which again, seems quite sub-optimal, and you cannot consider face-up because you don't have enough power for the cheapest token available (remember sorted so no point looking for another token that you might be able to face-up). Really, the problem with greedy algorithms is dealing with the doubt of guaranteed optimality, since the guarantee is only available if the local optimal leads to overall optimal, and that can be challenging to get a feel for, or even prove. This is one of the examples where the overall optimal choice is a bit more obvious, and it is also the locally optimal choice. But of course, there are also plenty of problems where it's very difficult to see why greedy works (why local optimal contributes to overall optimal). By learning about the properties of DP and greedy, when each is appropriate, and by building intuition with practice, you should be able to get a slight feel for when greedy or DP is more appropriate for a problem.
me who doesn't know dp and can only solve it greedy:
I see this as an absolute win
@@cs_randy Thanks.
@@leeroymlg4692 😂
You can actually stop the simulation once there is only one token left that cannot be used face up. This happens when left and right pointers meet at the same token. So if you add a conditional of left < right, you don’t need to update a res to a max score since the score variable will stop at the max and you can just break out. You do need to keep the whole loop as
exactly you just don't want to be greedy at the end if you have power do it else do not gamble on your score
7:42, did you mean to increase the power?
Edit: finished the video, you caught it.
Thank you for the daily leetcode problems. Great explanation as always.
anyone pls give the following approach a watch, and do let me know, why the recursive approach fails? (here, the idea is simple, incase power is atleast tokens[i], I reduce the power and increase the score, else if score>0 then I reduce the score but increase the power and else i skip. At last I return the max of the answers obtained)..
class Solution {
int f(vector& tokens,int p,int i,int score){
if(i==tokens.size()) return score;
int faceDown=-1e9;
int faceUp=-1e9;
if(p>=tokens[i]){
faceUp=f(tokens,p-tokens[i],i+1,score+1);
}
if(score>0){
faceDown=f(tokens,p+tokens[i],i+1,score-1);
}
int skip=f(tokens,p,i+1,score);
return max(skip,max(faceUp,faceDown));
}
public:
int bagOfTokensScore(vector& tokens, int power) {
return f(tokens,power,0,0);
}
};
Thank you for the explanation. I have a question regarding this problem. Initially, I attempted to solve it using dynamic programming, as we aim to maximize the score without sorting the tokens array. However, my solution was ineffective and not optimized, as it utilized a space complexity of O(n). Does dynamic programming conflict with a greedy approach in this context?
I actually solved this problem on my own. Later came to check out the video. It was almost the same code. Big thanks to neetcode sir!! Watching his videos daily is improving our problem solving skills.
Solved it on my own !! But the constraints might misguide you!!
I thought the question asked scanning from left to right...
Java Solution
class Solution {
public int bagOfTokensScore(int[] tokens, int power) {
int max = 0;
int i=0,j=tokens.length-1;
int t = 0;
Arrays.sort(tokens);
while ( i
NAVDEEP, YOU HAVE FORSAKEN ME
I was literally so close!!! except for keeping track of max everything was ditto!!
Hey love your stuff, I'm really interested in getting pro for a lifetime on your site... any idea when you would run the next promotion/discount? Would really appreciate it.
thought this was a backtracking solution, which worked for the test cases but got a time limit exceeded. Do you have any tips on how to recognize this as a two pointer vs backtracking?
What time do you upload this daily leetcode challenges? Because when I stuck and try to search your RUclips video about this problem, it's not there yet so i had to resort to the official leetcode solutions (luckily its not for premium).
Neety, please do 897. Increasing Order Search Tree!
Neetcode please suggest how can i improve my implementation skills, got the solution but stuck during writing code
I always come here to check if my solution can be improved, best channel out there! Thank you!
Little optimisation - if difference between left and right pointers = 1 we can just break out the loop since for sure will not increase total score.
I love you
Thank you so much
Great explanation
great video
if going to be a web developer in a small town in Europe., i would need to be able to solve medium leetcodes? or is easy enough
most companies ask easy
For web development, I would expect more take home assignments than code interview qs like this- but easy and maybe some easisr mediums are likely typical.
Good solution!
First like, and comment… still no MILITARY DISCOUNT 😂😂