Number of Music Playlists

Hard
892.

Number of Music Playlists

Number of Music Playlists is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon, Google and Spotify interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} goal
 * @param {number} k
 * @return {number}
 */
var numMusicPlaylists = function(n, goal, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Number of Music Playlists

  1. Hint 1

    The state is (songs placed so far, how many distinct songs have appeared).

  2. Hint 2

    The next slot either introduces a new song — n - j choices — or repeats an old one.

  3. Hint 3

    A repeat is only legal if at least k other songs sit in between, which leaves j - k choices.

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

  1. dp[i][j] is the number of playlists of length i using exactly j distinct songs.
  2. Adding a fresh song: dp[i-1][j-1] · (n - j + 1) — any of the songs not yet used.
  3. Repeating: dp[i-1][j] · (j - k) when j > k — any already-used song except the k most recent.
  4. 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]

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