Yeah that's fair. Old makes more sense to me since the two decisions we're making are old vs new songs, but its a little confusing either way. Better than i, j tho like most solutions on lc
Go the Mr Beast route.. Try doing leetcode under crazy scenarios, for e.g: 1. you can only use a mobile 2. you can type but you have to look at the screen from the mirror 3. you can press backspace only after each submission 4. code underwater etc. Go crazy, get more views will make you feel better for leaving your google job XD ( just kidding... you are the GOAT!)
i am still somewhat confused. is there a easier version of similar problem? also can anyone explain this line. res += (used_songs - k) * count(target - 1, used_songs) will this properly calculate combinations when goal is much bigger than n? in my head after getting playlist of length 2n it will not care about keeping k gaps.
honest question is it possible to solve a problem like this without seeing the solution prior? were u able to solve this without seeing the solution just based on your intuition?
Since we are working with the math in this solution, can you make a version of this solution that would generate all the playlist combinations? Or could you link a solution for a simillar problem? Im having a tought time accepting/ understanding the reason behind "no. of new songs that we have" in : res = (n-old_songs) * count(curr_goal-1 , old_songs+1)
think of it this way, n is the total of unique songs, old_song is the unique songs we have used so far, so theoretically, we have (n - old_song) of possible new/unused songs available to us.
Java recursion - Time limit exceeded solution: class Solution { int mod = 1_000_000_000 + 7; public int numMusicPlaylists(int n, int goal, int k) { return (int)count(goal, 0, n, k); } private long count(int curGoal, int oldSongs, int n, int k) { if(curGoal == 0 && oldSongs == n) //curGoal reached with exactly n songs. return 1; if(curGoal == 0 || oldSongs > n) //1. curGoal is reached but oldSongs !=n, 2. curGoal reached with oldsongs > n return 0; long picknew = 0; //choose new song picknew = (n - oldSongs ) * count(curGoal - 1, oldSongs + 1, n, k) ; // new songs = n - oldsongs. and new goal will be curGoal -1, and since we picked new song, it is now added to old songs, so old songs + 1
long pickOld = 0; //choose old song if(oldSongs > k) pickOld = (oldSongs - k ) * count(curGoal - 1, oldSongs, n, k) ; //we can pick oldsongs only if difference is k, curGoal decreases by 1 and since we did not pick new song, old songs count remains same.
Java memoization solution: class Solution { int mod = 1_000_000_000 + 7; long[][] memo; public int numMusicPlaylists(int n, int goal, int k) { memo = new long [goal + 1][n + 1]; //goal, oldSongs array. for(long[] arr: memo) { Arrays.fill(arr, -1); } return (int)count(goal, 0, n, k); } private long count(int curGoal, int oldSongs, int n, int k) { if(curGoal == 0 && oldSongs == n) //curGoal reached with exactly n songs. return 1; if(curGoal == 0 || oldSongs > n) //1. curGoal is reached but oldSongs !=n, 2. curGoal reached with oldsongs > n return 0; if(memo[curGoal][oldSongs] != -1) return memo[curGoal][oldSongs]; long picknew = 0; //choose new song picknew = (n - oldSongs ) * count(curGoal - 1, oldSongs + 1, n, k) ; // new songs = n - oldsongs. and new goal will be curGoal -1, and since we picked new song, it is now added to old songs, so old songs + 1
long pickOld = 0; //choose old song if(oldSongs > k) pickOld = (oldSongs - k ) * count(curGoal - 1, oldSongs, n, k) ; //we can pick oldsongs only if difference is k, curGoal decreases by 1 and since we did not pick new song, old songs count remains same.
Happy to see that you are back at leetcoding 💪
-leetcoding- neetcoding 😆
Unique makes more sense than old_songs
Yeah that's fair. Old makes more sense to me since the two decisions we're making are old vs new songs, but its a little confusing either way.
Better than i, j tho like most solutions on lc
@@NeetCodeIOthat's kind of clean code!
Missed your daily videos so much. Glad you're back 🥳
dontr stop uploading videos, you are the best
At 13:16 when you said I didn't explain "entirely". I'm like, bruh... you explain everything.
You're back!!
In second base case
Why we using old_songs > n rather than old_songs < n??
Go the Mr Beast route..
Try doing leetcode under crazy scenarios, for e.g:
1. you can only use a mobile
2. you can type but you have to look at the screen from the mirror
3. you can press backspace only after each submission
4. code underwater etc.
Go crazy, get more views will make you feel better for leaving your google job XD ( just kidding... you are the GOAT!)
i am still somewhat confused. is there a easier version of similar problem? also can anyone explain this line.
res += (used_songs - k) * count(target - 1, used_songs)
will this properly calculate combinations when goal is much bigger than n? in my head after getting playlist of length 2n it will not care about keeping k gaps.
welcome back
Thanks for the daily
Is it fine , if I was unable to solve this question after thinking a lot on my first try ?
honest question is it possible to solve a problem like this without seeing the solution prior? were u able to solve this without seeing the solution just based on your intuition?
I think no...😅
Since we are working with the math in this solution, can you make a version of this solution that would generate all the playlist combinations? Or could you link a solution for a simillar problem?
Im having a tought time accepting/ understanding the reason behind "no. of new songs that we have" in :
res = (n-old_songs) * count(curr_goal-1 , old_songs+1)
think of it this way, n is the total of unique songs, old_song is the unique songs we have used so far, so theoretically, we have (n - old_song) of possible new/unused songs available to us.
when will old_songs ever be > n?
Studying computer science would be much more difficult without you
Can anyone post the tabulation solution? having a bit of trouble with it.
Thanks for the providing the answer for daily
Day 2 Streak Maintained !!
:D can you share on how did you manage to do that?!
@@ngneerin 🥲🥲🥲🥲
Thanks for this better explanation ❤
Thank you. It helped a lot
In the first example, why can't [1,2,1] be the answer? since difference between last 1 and first 1 is k
Each playlist should have all songs from n mentioned atleast once. Since there is no 3 mentioned atleast once. it is not correct
Please drop more on Beginners's System Design on your Course🙏
Impressive work :)
Yesterday, I made the same wrong assumption about K songs. Eventually gave up on the problem.....
great video thanks
great explanation
Veri intutive bro... :)
I love you neetcode
Adding a Pair as Key in Hashmap is just not good, then you have to update its equals and hashCode
well, it seems like a middle school math problem with few extra steps. A few more.
This problem is a monster
nice!
Still not understood
Nuts
Password yaad aa gya achanak se?
hein?
Yes but i may forget it any day now 😝
@@NeetCodeIO use password manager 😎
❤
grab ur under 1k views ticket here
Java recursion - Time limit exceeded solution:
class Solution {
int mod = 1_000_000_000 + 7;
public int numMusicPlaylists(int n, int goal, int k) {
return (int)count(goal, 0, n, k);
}
private long count(int curGoal, int oldSongs, int n, int k) {
if(curGoal == 0 && oldSongs == n) //curGoal reached with exactly n songs.
return 1;
if(curGoal == 0 || oldSongs > n) //1. curGoal is reached but oldSongs !=n, 2. curGoal reached with oldsongs > n
return 0;
long picknew = 0;
//choose new song
picknew = (n - oldSongs ) * count(curGoal - 1, oldSongs + 1, n, k) ; // new songs = n - oldsongs. and new goal will be curGoal -1, and since we picked new song, it is now added to old songs, so old songs + 1
long pickOld = 0;
//choose old song
if(oldSongs > k)
pickOld = (oldSongs - k ) * count(curGoal - 1, oldSongs, n, k) ; //we can pick oldsongs only if difference is k, curGoal decreases by 1 and since we did not pick new song, old songs count remains same.
return (picknew % mod + pickOld % mod) % mod;
}
}
Java memoization solution:
class Solution {
int mod = 1_000_000_000 + 7;
long[][] memo;
public int numMusicPlaylists(int n, int goal, int k) {
memo = new long [goal + 1][n + 1]; //goal, oldSongs array.
for(long[] arr: memo) {
Arrays.fill(arr, -1);
}
return (int)count(goal, 0, n, k);
}
private long count(int curGoal, int oldSongs, int n, int k) {
if(curGoal == 0 && oldSongs == n) //curGoal reached with exactly n songs.
return 1;
if(curGoal == 0 || oldSongs > n) //1. curGoal is reached but oldSongs !=n, 2. curGoal reached with oldsongs > n
return 0;
if(memo[curGoal][oldSongs] != -1)
return memo[curGoal][oldSongs];
long picknew = 0;
//choose new song
picknew = (n - oldSongs ) * count(curGoal - 1, oldSongs + 1, n, k) ; // new songs = n - oldsongs. and new goal will be curGoal -1, and since we picked new song, it is now added to old songs, so old songs + 1
long pickOld = 0;
//choose old song
if(oldSongs > k)
pickOld = (oldSongs - k ) * count(curGoal - 1, oldSongs, n, k) ; //we can pick oldsongs only if difference is k, curGoal decreases by 1 and since we did not pick new song, old songs count remains same.
memo[curGoal][oldSongs] = (picknew % mod + pickOld % mod) % mod;
return memo[curGoal][oldSongs];
}
}