Number of Music Playlists - Solution & Explanation
Problem Statement
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
kother 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 109 + 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, hencedp[i][j] += dp[i - 1][j - 1] * (n - i + 1) - If we re-use one of the
isongs, consideringksongs must be between repeats, we have:dp[i][j] += dp[i][j - 1] * (i - k), wherei > k
This draws from the constraints on repeats and expands the playlist iteratively.
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.
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.
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.
Code
C++
JavaScript
Complexity
Time Complexity: O(n * goal), due to memoization.
Space Complexity: O(n * goal), for memo storage.
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.
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with State Definition | Time Complexity: O(n * goal), since we iterate through each subproblem. |
| Top-Down Dynamic Programming with Memoization | Time Complexity: O(n * goal), due to memoization. |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
Detailed 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 |
Video Solution
Number of Music Playlists - Leetcode 920 - Python • NeetCodeIO • 16,185 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Music Playlists easy or hard?
Number of Music Playlists Python/Java solution
How to solve Number of Music Playlists in O(n × goal)?
What is the best approach for Number of Music Playlists?
Is Number of Music Playlists asked at Google/Amazon/Meta?
What data structure is used in Number of Music Playlists?
What is the time complexity of Number of Music Playlists?
Ready to solve this problem?
Practice Number of Music Playlists with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor