Number of Music Playlists — Solution in Python, Java & C++
Number of Music Playlists solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Music Playlists is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon, Google and Spotify interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Google, Spotify
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have n different songs and want a playlist of exactly goal songs where:
- every song is played at least once;
- a song may be replayed only if at least
kother songs have been played since.
Return the number of possible playlists, modulo 10^9 + 7.
Example 1
Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: Every permutation of the three songs.
Example 2
Input: n = 2, goal = 3, k = 0
Output: 6
Example 3
Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: Only [1,2,1] and [2,1,2].
Constraints
0 <= k < n <= 100n <= goal <= 100
Hints for Number of Music Playlists
Hint 1
The state is (songs placed so far, how many distinct songs have appeared).
Hint 2
The next slot either introduces a new song —
n - jchoices — or repeats an old one.Hint 3
A repeat is only legal if at least
kother songs sit in between, which leavesj - kchoices.
How to solve Number of Music Playlists
Count by position, tracking how many distinct songs have been used. Each new slot is either a first-time song or a legal repeat, and both counts depend only on the state.
Approach
dp[i][j]is the number of playlists of lengthiusing exactlyjdistinct songs.- Adding a fresh song:
dp[i-1][j-1] · (n - j + 1)— any of the songs not yet used. - Repeating:
dp[i-1][j] · (j - k)whenj > k— any already-used song except thekmost recent. - The answer is
dp[goal][n], which forces every song to appear.
Why it works
The repeat count is j - k because exactly the last k distinct songs played are blocked, and with j distinct songs already used there are j - k legal choices — a count that does not depend on which songs those were, which is what keeps the state small. Requiring j = n at the end enforces the 'every song at least once' rule without a separate inclusion-exclusion step.
Complexity
- Time —
O(goal · n) - Space —
O(goal · n)
Pitfalls
dp[i-1][j] · (j - k)must be skipped whenj <= k, or the count goes negative.- The products reach about
10^9 · 100, so the multiplication needs 64-bit before the modulo. k = 0allows immediate repeats and is a legal input.
Reference solution
Python
def numMusicPlaylists(n: int, goal: int, k: int) -> int:
MOD = 1000000007
dp = [[0] * (n + 1) for _ in range(goal + 1)]
dp[0][0] = 1
for i in range(1, goal + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i - 1][j - 1] * (n - j + 1) % MOD
if j > k:
dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - k)) % MOD
return dp[goal][n]Java
public static int numMusicPlaylists(int n, int goal, int k) {
final long MOD = 1000000007L;
long[][] dp = new long[goal + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i <= goal; i++) {
for (int j = 1; j <= n; j++) {
long v = dp[i - 1][j - 1] * (n - j + 1) % MOD;
if (j > k) v = (v + dp[i - 1][j] * (j - k)) % MOD;
dp[i][j] = v;
}
}
return (int) dp[goal][n];
}C++
int numMusicPlaylists(int n, int goal, int k) {
const long long MOD = 1000000007LL;
vector<vector<long long>> dp(goal + 1, vector<long long>(n + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= goal; i++) {
for (int j = 1; j <= n; j++) {
long long v = dp[i - 1][j - 1] * (n - j + 1) % MOD;
if (j > k) v = (v + dp[i - 1][j] * (j - k)) % MOD;
dp[i][j] = v;
}
}
return (int) dp[goal][n];
}JavaScript
var numMusicPlaylists = function(n, goal, k) {
var MOD = 1000000007;
var dp = [];
for (var a = 0; a <= goal; a++) {
var row = [];
for (var b = 0; b <= n; b++) row.push(0);
dp.push(row);
}
dp[0][0] = 1;
for (var i = 1; i <= goal; i++) {
for (var j = 1; j <= n; j++) {
var v = dp[i - 1][j - 1] * (n - j + 1) % MOD;
if (j > k) v = (v + dp[i - 1][j] * (j - k)) % MOD;
dp[i][j] = v;
}
}
return dp[goal][n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming