920. Number of Music Playlists - Solution & Explanation

The problem

Your music player contains n different songs. You want to listen to goal songs (not necessarily different) during your trip. To avoid boredom, you will create a playlist so that:

Every song is played at least once.
A song can only be played again only if k other songs have been played.

Given n, goal, and k, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

Example 2:

Input: n = 2, goal = 3, k = 0
Output: 6
Explanation: There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].

Example 3:

Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].

Constraints:

0 <= k < n <= goal <= 100

Approach overview

Problem Overview: You need to count how many playlists of length goal can be created using n unique songs where every song appears at least once and a song can only repeat after k other songs have played. The result must be returned modulo 1e9 + 7. The challenge is enforcing both constraints: using all songs and respecting the repeat gap.

Approach 1: Dynamic Programming with State Definition (O(n × goal) time, O(n × goal) space)

Define dp[i][j] as the number of playlists of length i that contain exactly j unique songs. Two choices exist when building the playlist. First, add a new song that hasn't appeared yet. There are n - (j - 1) options, so transition from dp[i-1][j-1]. Second, replay an existing song, but only those not used in the last k positions. That leaves max(j - k, 0) valid songs, transitioning from dp[i-1][j]. Iterate i from 1 to goal and j from 1 to n. This bottom‑up dynamic programming formulation cleanly enforces both constraints and is the standard interview solution.

Approach 2: Top-Down Dynamic Programming with Memoization (O(n × goal) time, O(n × goal) space)

The same recurrence can be implemented recursively with memoization. Define a function dfs(i, j) representing playlists of length i using j unique songs. Recursively compute the two transitions: add a new song (n - j choices) or reuse an old song (max(j - k, 0) choices). Cache results in a memo table to avoid recomputation. This top‑down style is often easier to reason about because the recurrence mirrors the problem definition directly. The technique combines dynamic programming with recursion and works well when you want clear state transitions without manually filling a table.

Combinatorics Insight: The DP works because it separates the problem into counting playlists by how many unique songs have been introduced so far. Each step either introduces a new element from the remaining pool or reuses an eligible one that satisfies the k-distance rule. This perspective connects the problem to counting permutations with constraints, a common theme in combinatorics and math-driven DP problems.

Recommended for interviews: The bottom‑up DP with state dp[i][j] is what most interviewers expect. It demonstrates you can design states, derive transitions, and enforce constraints mathematically. Mentioning the recursive memoized version shows strong understanding of the recurrence and flexibility in implementation.

Approach 1: Dynamic Programming with State Definition

We define a dynamic programming approach where we use a 2D DP table where dp[i][j] means the number of ways to form a playlist of length j using i distinct songs. We will eventually find dp[n][goal].

The key recurrence relations are:

If we choose a fresh song, there are (n - i + 1) songs available, hence dp[i][j] += dp[i - 1][j - 1] * (n - i + 1)
If we re-use one of the i songs, considering k songs must be between repeats, we have: dp[i][j] += dp[i][j - 1] * (i - k), where i > k

This draws from the constraints on repeats and expands the playlist iteratively.

Python


MOD = 10**9 + 7
def numMusicPlaylists(n, goal, k):
    dp = [[0] * (goal + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(1, goal + 1):
            dp[i][j] = dp[i - 1][j - 1] * (n - i + 1) % MOD
            if i > k:
                dp[i][j] += dp[i][j - 1] * (i - k) % MOD
            dp[i][j] %= MOD
    return dp[n][goal]

Java


class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        int MOD = 1000000007;
        long[][] dp = new long[n + 1][goal + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= goal; ++j) {
                dp[i][j] = dp[i - 1][j - 1] * (n - i + 1) % MOD;
                if (i > k) {
                    dp[i][j] += dp[i][j - 1] * (i - k) % MOD;
                }
                dp[i][j] %= MOD;
            }
        }
        return (int)dp[n][goal];
    }
}

The solution uses a 2D list to store the number of ways to create a playlist of length j with i distinct songs. The state transition involves adding a new song or reusing one respecting the separation condition. The final solution is found at dp[n][goal].

Complexity

Time Complexity: O(n * goal), since we iterate through each subproblem.
Space Complexity: O(n * goal), due to the size of the DP table.

Try this approach in the editor

Approach 2: Top-Down Dynamic Programming with Memoization

This approach uses memoization to recursively compute the number of playlists. It calculates the playlists by considering whether a new song is added or an existing song is reused, accounting for k intervening songs.

C++


#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
vector<vector<int>> memo;

int totalPlaylists(int n, int goal, int k, int i, int j) {
    if (j == 0) return i == 0 ? 1 : 0;
    if (memo[i][j] != -1) return memo[i][j];
    long res = (totalPlaylists(n, goal, k, i - 1, j - 1) * (n - i + 1)) % MOD;
    if (i > k) {
        res = (res + totalPlaylists(n, goal, k, i, j - 1) * (i - k)) % MOD;
    }
    return memo[i][j] = res;
}

int numMusicPlaylists(int n, int goal, int k) {
    memo = vector<vector<int>>(n + 1, vector<int>(goal + 1, -1));
    return totalPlaylists(n, goal, k, n, goal);
}

JavaScript


const numMusicPlaylists = (n, goal, k) => {
    const MOD = 1e9 + 7;
    const memo = Array.from({ length: n + 1 }, () => Array(goal + 1).fill(undefined));
    
    const countPlaylists = (i, j) => {
        if (j === 0) return i === 0 ? 1 : 0;
        if (memo[i][j] !== undefined) return memo[i][j];
        let result = (countPlaylists(i - 1, j - 1) * (n - i + 1)) % MOD;
        if (i > k) {
            result = (result + countPlaylists(i, j - 1) * (i - k)) % MOD;
        }
        return memo[i][j] = result;
    };
    return countPlaylists(n, goal);
};

This C++ solution uses recursion with memoization to calculate the number of playlists. The function totalPlaylists recursively solves the problem by either adding new songs or reusing existing ones, with memoization avoiding redundant calculations.

Complexity

Time Complexity: O(n * goal), due to memoization.
Space Complexity: O(n * goal), for memo storage.

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][j] to be the number of playlists that can be made from i songs with exactly j different songs. We have f[0][0] = 1 and the answer is f[goal][n].

For f[i][j], we can choose a song that we have not listened before, so the previous state is f[i - 1][j - 1], and there are n - (j - 1) = n - j + 1 options. Thus, f[i][j] += f[i - 1][j - 1] times (n - j + 1). We can also choose a song that we have listened before, so the previous state is f[i - 1][j], and there are j - k options. Thus, f[i][j] += f[i - 1][j] times (j - k), where j geq k.

Therefore, we have the transition equation:

$f[i][j] = \begin{cases} 1 & i = 0, j = 0 \ f[i - 1][j - 1] times (n - j + 1) + f[i - 1][j] times (j - k) & i geq 1, j geq 1 \end{cases}

The final answer is f[goal][n].

The time complexity is O(goal times n), and the space complexity is O(goal times n). Here, goal and n$ are the parameters given in the problem.

TypeScript

function numMusicPlaylists(n: number, goal: number, k: number): number {
    const mod = 1e9 + 7;
    const f = new Array(goal + 1).fill(0).map(() => new Array(n + 1).fill(0));
    f[0][0] = 1;
    for (let i = 1; i <= goal; ++i) {
        for (let j = 1; j <= n; ++j) {
            f[i][j] = f[i - 1][j - 1] * (n - j + 1);
            if (j > k) {
                f[i][j] += f[i - 1][j] * (j - k);
            }
            f[i][j] %= mod;
        }
    }
    return f[goal][n];
}

func numMusicPlaylists(n int, goal int, k int) int {
	const mod = 1e9 + 7
	f := make([][]int, goal+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	f[0][0] = 1
	for i := 1; i <= goal; i++ {
		for j := 1; j <= n; j++ {
			f[i][j] = f[i-1][j-1] * (n - j + 1)
			if j > k {
				f[i][j] += f[i-1][j] * (j - k)
			}
			f[i][j] %= mod
		}
	}
	return f[goal][n]
}

Rust

impl Solution {
    #[allow(dead_code)]
    pub fn num_music_playlists(n: i32, goal: i32, k: i32) -> i32 {
        let mut dp: Vec<Vec<i64>> = vec![vec![0; n as usize + 1]; goal as usize + 1];

        // Initialize the dp vector
        dp[0][0] = 1;

        // Begin the dp process
        for i in 1..=goal as usize {
            for j in 1..=n as usize {
                // Choose the song that has not been chosen before
                // We have n - (j - 1) songs to choose
                dp[i][j] += dp[i - 1][j - 1] * ((n - ((j as i32) - 1)) as i64);

                // Choose the song that has been chosen before
                // We have j - k songs to choose if j > k
                if (j as i32) > k {
                    dp[i][j] += dp[i - 1][j] * (((j as i32) - k) as i64);
                }

                // Update dp[i][j]
                dp[i][j] %= ((1e9 as i32) + 7) as i64;
            }
        }

        dp[goal as usize][n as usize] as i32
    }
}

Try this approach in the editor

Approach 4: Dynamic Programming (Space Optimization)

We notice that f[i][j] is only related to f[i - 1][j - 1] and f[i - 1][j]. Therefore, we can use a rolling array to optimize the space complexity, reducing the space complexity to O(n).

TypeScript

function numMusicPlaylists(n: number, goal: number, k: number): number {
    const mod = 1e9 + 7;
    let f = new Array(goal + 1).fill(0);
    f[0] = 1;
    for (let i = 1; i <= goal; ++i) {
        const g = new Array(goal + 1).fill(0);
        for (let j = 1; j <= n; ++j) {
            g[j] = f[j - 1] * (n - j + 1);
            if (j > k) {
                g[j] += f[j] * (j - k);
            }
            g[j] %= mod;
        }
        f = g;
    }
    return f[n];
}

func numMusicPlaylists(n int, goal int, k int) int {
	const mod = 1e9 + 7
	f := make([]int, goal+1)
	f[0] = 1
	for i := 1; i <= goal; i++ {
		g := make([]int, goal+1)
		for j := 1; j <= n; j++ {
			g[j] = f[j-1] * (n - j + 1)
			if j > k {
				g[j] += f[j] * (j - k)
			}
			g[j] %= mod
		}
		f = g
	}
	return f[n]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with State Definition	Time Complexity: O(n * goal), since we iterate through each subproblem. Space Complexity: O(n * goal), due to the size of the DP table.
Top-Down Dynamic Programming with Memoization	Time Complexity: O(n * goal), due to memoization. Space Complexity: O(n * goal), for memo storage.
Dynamic Programming	–
Dynamic Programming (Space Optimization)	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with State Definition (Bottom-Up)	O(n × goal)	O(n × goal)	Standard solution for interviews; clear state transitions and deterministic iteration
Top-Down DP with Memoization	O(n × goal)	O(n × goal)	When recursion makes the recurrence easier to express or reason about

Frequently asked questions

Is Number of Music Playlists easy or hard?

LeetCode classifies Number of Music Playlists as a Hard problem. The difficulty comes from designing the correct DP state and handling the k-repeat constraint mathematically rather than through simulation.

Number of Music Playlists Python/Java solution

Both Python and Java implementations follow the same DP recurrence. Use a 2D array dp[goal+1][n+1], iterate through playlist length and unique songs, and apply the transition for adding a new song or replaying an eligible song while applying modulo 1e9+7.

How to solve Number of Music Playlists in O(n × goal)?

Define dp[i][j] as the number of playlists of length i using j unique songs. Transition by adding a new song from the unused set or replaying an existing song that satisfies the k-gap rule. The recurrence is dp[i][j] = dp[i-1][j-1] * (n - (j-1)) + dp[i-1][j] * max(j - k, 0), computed modulo 1e9+7.

What is the best approach for Number of Music Playlists?

Dynamic programming with state dp[i][j] is the standard approach. The state tracks playlists of length i that contain j unique songs. Each step either adds a new song or replays an existing song that is at least k positions away. This solution runs in O(n × goal) time and O(n × goal) space.

Is Number of Music Playlists asked at Google/Amazon/Meta?

This problem appears in interview preparation lists for companies that test strong dynamic programming skills, including Google, Amazon, and Meta-style interview rounds. It evaluates state design, combinatorics reasoning, and careful transition logic.

What data structure is used in Number of Music Playlists?

The core structure is a 2D dynamic programming table or a memoization map storing states (playlist length, unique songs used). The algorithm relies on counting transitions rather than traditional data structures like heaps or trees.

What is the time complexity of Number of Music Playlists?

The optimal dynamic programming solution runs in O(n × goal) time because the DP table iterates through every playlist length from 1..goal and every possible count of unique songs from 1..n. Space complexity is O(n × goal) for storing the DP states.

Number of Music Playlists solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with State Definition

Approach 2: Top-Down Dynamic Programming with Memoization

Approach 3: Dynamic Programming

Approach 4: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Number of Music Playlists solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with State Definition

Approach 2: Top-Down Dynamic Programming with Memoization

Approach 3: Dynamic Programming

Approach 4: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems