Number of Music Playlists - Leetcode 920 - Python

Solving Leetcode 920 - Number of Music Playlists, today's daily leetcode on August 5.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/number-...
0:00 - Read the problem
1:30 - Drawing Explanation
13:30 - Coding Explanation
leetcode 920
#neetcode #leetcode #python

[@YeetusOfHouseFetus]

Return of the king 🙇‍♂️

[@Cheng-K]

Happy to see that you are back at leetcoding 💪

[@sprajosh]

-leetcoding- neetcoding 😆

[@umanganant983]

Missed your daily videos so much. Glad you're back 🥳

[@peakpotential9]

Unique makes more sense than old_songs

[@NeetCodeIO]

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

[@rkalyankumar]

​@@NeetCodeIOthat's kind of clean code!

[@xixixitsme]

dontr stop uploading videos, you are the best

[@aadil4236]

You're back!!

[@uptwist2260]

Thanks for the daily

[@HarshPranami]

Thank you. It helped a lot

[@user-jk4gi3gi8k]

Thanks for this better explanation ❤

[@chaopeter9690]

Thanks for the providing the answer for daily

[@ialgorithms]

At 13:16 when you said I didn't explain "entirely". I'm like, bruh... you explain everything.

[@jeevansammeswarsiddaboena99]

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

[@Vancha112]

Impressive work :)

[@pseudocod3r]

welcome back

[@krateskim4169]

great video thanks

[@krzychugiwera2509]

Studying computer science would be much more difficult without you

[@kwakukusi4094]

great explanation

[@nahidtanvir5901]

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.

[@krishnasharma657]

In second base case
Why we using old_songs > n rather than old_songs < n??

[@dhanesh.s]

Please drop more on Beginners's System Design on your Course🙏

[@amansharma7668]

Veri intutive bro... :)

[@satyamjha68]

Is it fine , if I was unable to solve this question after thinking a lot on my first try ?

[@AMX0013]

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)

[@rowanus116]

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.

[@juda550]

I love you neetcode

[@JM_utube]

when will old_songs ever be > n?

[@yeah5037]

nice!

[@demonrock3322]

Can anyone post the tabulation solution? having a bit of trouble with it.

[@MrZiyak99]

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?

[@user-le6ts6ci7h]

I think no...😅

[@sumitsharma6738]

Day 2 Streak Maintained !!

[@ngneerin]

:D can you share on how did you manage to do that?!

[@sumitsharma6738]

@@ngneerin 🥲🥲🥲🥲

[@MiguelLopez-ph4qb]

Nuts

[@akankshasharma7498]

Yesterday, I made the same wrong assumption about K songs. Eventually gave up on the problem.....

[@MrKB_SSJ2]

This problem is a monster

[@parashararamesh4252]

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!)

[@art4eigen93]

well, it seems like a middle school math problem with few extra steps. A few more.

[@sumitsharma6738]

Adding a Pair as Key in Hashmap is just not good, then you have to update its equals and hashCode

[@chilakalahithesh2259]

❤

[@atharvakulkarni2180]

In the first example, why can't [1,2,1] be the answer? since difference between last 1 and first 1 is k

[@karthickraja1760]

Each playlist should have all songs from n mentioned atleast once. Since there is no 3 mentioned atleast once. it is not correct

[@AftabAlam-gh1nh]

Still not understood

[@xiaoshen194]

Password yaad aa gya achanak se?

[@sumitsharma6738]

hein?

[@NeetCodeIO]

Yes but i may forget it any day now 😝

[@abhaytiwari5991]

@@NeetCodeIO use password manager 😎

[@aditya-lr2in]

grab ur under 1k views ticket here

[@divyagracie]

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];
}
}

[@divyagracie]

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;
}
}