Number of Music Playlists
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach solves the problem using recursion with memoization, which is a top-down dynamic programming technique. We define a function solve(i, j) that calculates the number of playlists of length i containing exactly j unique songs. To avoid recomputing results for the same state (i, j), we store them in a 2D memoization table.
Algorithm
- Define a recursive function
solve(i, j)that computes the number of playlists of lengthiwithjunique songs. - Use a 2D array
memoof size(goal + 1) x (n + 1)for memoization, initialized with a sentinel value (e.g., -1). - Implement the base cases for the recursion:
- If
i == 0andj == 0, return 1 (one way to have an empty playlist). - If
i == 0orj == 0, return 0 (it's impossible to form a playlist under these conditions). - Also, if
j > norj > i, it's an invalid state, so return 0.
- If
- In the
solve(i, j)function, first check if the result is already inmemo. If so, return it. - Otherwise, compute the result using the recurrence relation:
- Case 1 (New Song): The last song is a new one. This is possible if we had a playlist of length
i-1withj-1unique songs. There aren - (j-1)choices for this new song. The number of ways issolve(i - 1, j - 1) * (n - j + 1). - Case 2 (Repeated Song): The last song is a repeat. This is possible if we had a playlist of length
i-1withjunique songs. The number of available songs to repeat ismax(0, j - k). The number of ways issolve(i - 1, j) * (j - k)(only ifj > k).
- Case 1 (New Song): The last song is a new one. This is possible if we had a playlist of length
- Sum the results from both cases (modulo
10^9 + 7), store it inmemo[i][j], and return it. - The initial call to start the process is
solve(goal, n).
Walkthrough
The core idea is to build the playlist song by song and keep track of its length (i) and the number of unique songs used (j). When we want to determine the number of playlists for state (i, j), we consider the i-th song we are adding.
There are two possibilities for this song:
-
It's a new, unique song. For this to happen, the first
i-1songs must have formed a playlist withj-1unique songs. We can then pick any of then - (j-1)songs that haven't been used yet. The number of ways for this case issolve(i - 1, j - 1) * (n - j + 1). -
It's a repetition of a song already in the playlist. For this, the first
i-1songs must have already containedjunique songs. The constraint is that a song can be replayed only ifkother songs have been played since its last appearance. Withjunique songs available, we can choose any of them to repeat, except for thekmost recent unique songs played. This gives usj - kchoices for the song to repeat. This is only possible ifj > k. The number of ways for this case issolve(i - 1, j) * (j - k).
The total number of ways for solve(i, j) is the sum of these two cases. We use a memo table to store and retrieve previously computed results, preventing redundant calculations.
class Solution { long[][] memo; int N, K; long MOD = 1_000_000_007; public int numMusicPlaylists(int n, int goal, int k) { this.N = n; this.K = k; this.memo = new long[goal + 1][n + 1]; for (long[] row : memo) { java.util.Arrays.fill(row, -1); } return (int) solve(goal, n); } private long solve(int i, int j) { // A playlist of length i with j unique songs if (i == 0 && j == 0) { return 1; } if (i == 0 || j == 0) { return 0; } if (memo[i][j] != -1) { return memo[i][j]; } // Case 1: The last song is a new song. // We had a playlist of length i-1 with j-1 unique songs. // We choose one of the (N - (j-1)) new songs. long res = solve(i - 1, j - 1) * (N - j + 1); res %= MOD; // Case 2: The last song is a repetition of an existing song. // We had a playlist of length i-1 with j unique songs. // We can repeat a song if j > K. The number of songs we can choose from is (j - K). if (j > K) { res += solve(i - 1, j) * (j - K); res %= MOD; } return memo[i][j] = res; }}Complexity
Time
O(goal * n) - Each state `(i, j)` is computed only once due to memoization. There are `goal * n` possible states.
Space
O(goal * n) - This is for the memoization table. The recursion depth can also go up to `goal`, contributing to the call stack space.
Trade-offs
Pros
The logic directly translates the recurrence relation, making it intuitive to understand.
It only computes states that are reachable from the initial call, which can be more efficient if the state space is sparse.
Cons
May lead to a
StackOverflowErrorfor very largegoalvalues, though not an issue with the given constraints.Generally has slightly more overhead than the iterative (tabulation) approach due to recursive function calls.
This approach uses bottom-up dynamic programming, also known as tabulation. We build the solution iteratively by filling a 2D table dp[i][j], where i represents the playlist length and j represents the number of unique songs. We start from the base case (an empty playlist) and compute the values for larger playlists based on the results of smaller ones.
Algorithm
- Create a 2D DP table
dpof size(goal + 1) x (n + 1)to store the number of playlists.dp[i][j]will store the number of playlists of lengthiwithjunique songs. - Initialize the base case:
dp[0][0] = 1, representing one empty playlist of length 0 with 0 unique songs. - Iterate through playlist lengths
ifrom 1 togoal. - For each
i, iterate through the number of unique songsjfrom 1 ton(andj <= i). - Calculate
dp[i][j]using the values from the previous row (i-1):- Add a new song:
dp[i-1][j-1] * (n - j + 1). This term represents taking a playlist of lengthi-1withj-1unique songs and adding one of then-(j-1)unused songs. - Replay an existing song:
dp[i-1][j] * (j - k). This term represents taking a playlist of lengthi-1withjunique songs and replaying one of thej-ksongs that are not restricted by thekconstraint. This is only added ifj > k.
- Add a new song:
- Sum these two terms (modulo
10^9 + 7) to getdp[i][j]. - The final answer is the value in
dp[goal][n].
Walkthrough
We define dp[i][j] as the number of possible playlists of length i that contain exactly j unique songs. Our goal is to find dp[goal][n]. We build this table starting from dp[0][0] = 1.
For each cell dp[i][j], we consider how it could have been formed by adding the i-th song:
-
The
i-th song is a new song: We must have started with a playlist of lengthi-1withj-1unique songs. There aredp[i-1][j-1]such playlists. We can choose any of then - (j-1)songs not yet used. So, this contributesdp[i-1][j-1] * (n - j + 1)todp[i][j]. -
The
i-th song is a repeated song: We must have started with a playlist of lengthi-1withjunique songs. There aredp[i-1][j]such playlists. We can repeat any of thejsongs, but to satisfy the constraint, we cannot repeat a song that was played too recently. The number of available songs to repeat isj - k. This is only possible ifj > k. This contributesdp[i-1][j] * (j - k)todp[i][j].
The recurrence relation is:
dp[i][j] = (dp[i-1][j-1] * (n - j + 1)) + (dp[i-1][j] * max(0, j - k))
We fill the table row by row, and the final answer is dp[goal][n].
class Solution { public int numMusicPlaylists(int n, int goal, int k) { long MOD = 1_000_000_007; 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++) { // Case 1: Add a new song // Comes from a playlist of length i-1 with j-1 unique songs. dp[i][j] += dp[i - 1][j - 1] * (n - j + 1); dp[i][j] %= MOD; // Case 2: Replay an existing song // Comes from a playlist of length i-1 with j unique songs. if (j > k) { dp[i][j] += dp[i - 1][j] * (j - k); dp[i][j] %= MOD; } } } return (int) dp[goal][n]; }}Complexity
Time
O(goal * n) - We iterate through a `goal x n` grid to fill the DP table.
Space
O(goal * n) - For the 2D DP table.
Trade-offs
Pros
Avoids recursion overhead and the risk of stack overflow, making it slightly faster and more robust than the recursive approach.
The iterative nature of filling the table is often straightforward to implement and debug.
Cons
Requires
O(goal * n)space, which is less optimal than the space-optimized version, although acceptable for the given constraints.
This approach optimizes the 2D DP solution by reducing its space complexity. We observe that to compute the values for the current playlist length i, we only need the results from the previous length i-1. This allows us to use only a 1D array to store the DP states, bringing the space complexity down from O(goal * n) to O(n).
Algorithm
- Initialize a 1D array
dpof sizen + 1.dp[j]will store the number of playlists of the current length withjunique songs. - Set the base case:
dp[0] = 1for a playlist of length 0. - Iterate
ifrom 1 togoal(for playlist length). - Inside this loop, iterate
jfromndown to 1. A backward loop is crucial to ensure that when we calculatedp[j], we are usingdp[j]anddp[j-1]from the previous iteration (i-1). - Update
dp[j]using the same recurrence relation:dp[j] = (dp[j-1] * (n - j + 1)) + (dp[j] * (j - k))(ifj > k). - After the inner
jloop finishes for a giveni, we must setdp[0] = 0. This is because for any playlist of lengthi > 0, it's impossible to have 0 unique songs. This correctly sets updp[0]for the next iteration's calculation ofdp[1]. - After the outer loop completes,
dp[n]will hold the number of playlists of lengthgoalwithnunique songs.
Walkthrough
Instead of a full 2D table, we use a single 1D array, dp, of size n+1. dp[j] will store the number of playlists for the current length i with j unique songs.
As we iterate from i = 1 to goal, we update this dp array. The key challenge is that the update rule for dp[j] depends on both dp[j] and dp[j-1] from the previous iteration. If we update in-place with a forward j loop, dp[j-1] would be overwritten before it's used to calculate dp[j].
To solve this, we iterate j from n down to 1. When we compute the new dp[j], the values dp[j] and dp[j-1] on the right-hand side of the equation are still the values from the previous i iteration, which is exactly what we need.
Another subtlety is handling dp[0]. dp[0] is initially 1 (for i=0, j=0). However, for any i > 0, dp[i][0] should be 0. We must manually set dp[0] = 0 after the first iteration to ensure correct calculations for subsequent steps.
class Solution { public int numMusicPlaylists(int n, int goal, int k) { long MOD = 1_000_000_007; long[] dp = new long[n + 1]; dp[0] = 1; for (int i = 1; i <= goal; i++) { // Iterate j backwards to use dp array from the previous state (i-1). for (int j = n; j >= 1; j--) { // Case 1: Add a new song long term1 = dp[j - 1] * (n - j + 1); // Case 2: Replay an existing song long term2 = 0; if (j > k) { term2 = dp[j] * (j - k); } dp[j] = (term1 + term2) % MOD; } // For any playlist of length i > 0, it's impossible to have 0 unique songs. // This sets up dp[0] for the next iteration's calculation of dp[1]. dp[0] = 0; } return (int) dp[n]; }}Complexity
Time
O(goal * n) - The number of computations remains the same as the 2D DP approach.
Space
O(n) - We only need a single 1D array of size `n+1` to store the DP states.
Trade-offs
Pros
Highly space-efficient, using only
O(n)space.Maintains the optimal time complexity of
O(goal * n).
Cons
The logic, especially with the single-array optimization and backward iteration, can be less intuitive to grasp compared to the 2D DP approach.
Solutions
Solution
class Solution {public int numMusicPlaylists(int n, int goal, int k) { final int mod = (int)1 e9 + 7; long[][] f = new long[goal + 1][n + 1]; f[0][0] = 1; for (int i = 1; i <= goal; ++i) { for (int 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 (int)f[goal][n]; }}class Solution {public: int numMusicPlaylists(int n, int goal, int k) { const int mod = 1e9 + 7; long long f[goal + 1][n + 1]; memset(f, 0, sizeof(f)); f[0][0] = 1; for (int i = 1; i <= goal; ++i) { for (int 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]; }};class Solution: def numMusicPlaylists(self, n: int, goal: int, k: int) -> int: mod = 10 ** 9 + 7 f = [[0] * (n + 1) for _ in range(goal + 1)] f[0][0] = 1 for i in range(1, goal + 1): for j in range(1, n + 1): 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]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.