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:
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 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 <= 100Problem 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.
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:
(n - i + 1) songs available, hence dp[i][j] += dp[i - 1][j - 1] * (n - i + 1)i songs, considering k songs must be between repeats, we have: dp[i][j] += dp[i][j - 1] * (i - k), where i > kThis 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].
Time Complexity: O(n * goal), since we iterate through each subproblem.
Space Complexity: O(n * goal), due to the size of the DP table.
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.
C++
JavaScript
Time Complexity: O(n * goal), due to memoization.
Space Complexity: O(n * goal), for memo storage.
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.
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).
Python
Java
C++
Go
TypeScript
| 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) | — |
| 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 |
Number of Music Playlists - Leetcode 920 - Python • NeetCodeIO • 15,833 views views
Watch 9 more video solutions →Practice Number of Music Playlists with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor