Number of Music Playlists — Hard Problem & Solution

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 k…

Difficulty: Hard
Topics: Math, Dynamic Programming, 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 k other 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 <= 100
n <= goal <= 100

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 length i using exactly j distinct 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) when j > k — any already-used song except the k most 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 when j <= k, or the count goes negative.
The products reach about 10^9 · 100, so the multiplication needs 64-bit before the modulo.
k = 0 allows 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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue