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
I am thinking why did you stopped making videos in Neetcode ............ Now I got . Just now solving that problem and searched for the solution , then i have seen your new channel
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.
Return of the king 🙇♂️
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 🥳
I am thinking why did you stopped making videos in Neetcode ............ Now I got . Just now solving that problem and searched for the solution , then i have seen your new channel
In second base case
Why we using old_songs > n rather than old_songs < n??
At 13:16 when you said I didn't explain "entirely". I'm like, bruh... you explain everything.
Thanks for the daily
dontr stop uploading videos, you are the best
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?
I think no...😅
when will old_songs ever be > n?
Day 2 Streak Maintained !!
:D can you share on how did you manage to do that?!
@@ngneerin 🥲🥲🥲🥲
Thanks for the providing the answer for daily
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.
Is it fine , if I was unable to solve this question after thinking a lot on my first try ?
You're back!!
Please drop more on Beginners's System Design on your Course🙏
Thanks for this better explanation ❤
Thank you. It helped a lot
Studying computer science would be much more difficult without you
Can anyone post the tabulation solution? having a bit of trouble with it.
welcome back
great explanation
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
great video thanks
Impressive work :)
Veri intutive bro... :)
Adding a Pair as Key in Hashmap is just not good, then you have to update its equals and hashCode
I love you neetcode
This problem is a monster
Yesterday, I made the same wrong assumption about K songs. Eventually gave up on the problem.....
Password yaad aa gya achanak se?
hein?
Yes but i may forget it any day now 😝
@@NeetCodeIO use password manager 😎
well, it seems like a middle school math problem with few extra steps. A few more.
Nuts
nice!
Still not understood
❤
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];
}
}