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