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 <= 100The key idea in #920 Number of Music Playlists is to count how many valid playlists of length L can be formed using N unique songs, while ensuring that a song can only repeat after at least K other songs have been played. This constraint makes brute-force enumeration impractical, so a dynamic programming approach is used.
Define dp[i][j] as the number of playlists of length i that contain exactly j unique songs. At each step, you either add a new song (one that hasn’t appeared yet) or replay an old song that is not within the last K positions. The transitions combine counting logic with combinatorics to track how many choices remain for each action.
The final answer comes from building the DP table until the playlist length reaches L and all N songs have been used. This method efficiently handles constraints by systematically counting valid states instead of generating playlists.
Time Complexity: O(N × L)
Space Complexity: O(N × L) (can be optimized to O(N)).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Combinatorics | O(N × L) | O(N × L) |
| Space Optimized DP | O(N × L) | O(N) |
NeetCodeIO
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.
Time Complexity: O(n * goal), since we iterate through each subproblem.
Space Complexity: O(n * goal), due to the size of the DP table.
1
2MOD = 10**9 + 7
3def numMusicPlaylists(n, goal, k):
4 dp = [[0] * (goal + 1) for _ in range(n + 1)]
5 dp[0][0] = 1
6 for i in range(1, n + 1):
7 for j in range(1, goal + 1):
8 dp[i][j] = dp[i - 1][j - 1] * (n - i + 1) % MOD
9 if i > k:
10 dp[i][j] += dp[i][j - 1] * (i - k) % MOD
11 dp[i][j] %= MOD
12 return dp[n][goal]
13The 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].
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.
Time Complexity: O(n * goal), due to memoization.
Space Complexity: O(n * goal), for memo storage.
1
2#include <vector>
3using namespace std;
4const int MOD = 1e9 + 7;
5vector<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);
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of combinatorics and dynamic programming counting problems like this can appear in FAANG-style interviews. They test a candidate's ability to design state transitions and handle constraints efficiently.
A 2D dynamic programming table is the most suitable structure for this problem. It helps track the number of playlists for each length and number of unique songs used, making it easier to apply the recurrence relations.
The optimal approach uses dynamic programming combined with combinatorics. Define dp[i][j] as the number of playlists of length i containing j unique songs, and update it by considering whether the next song is new or a previously played one that satisfies the K-gap constraint.
The difficulty comes from combining multiple concepts such as dynamic programming, combinatorics, and constraint handling. Candidates must carefully model the state transitions to ensure songs are only repeated after at least K other 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.