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 <= 100We 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].
Java
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.
JavaScript
Time Complexity: O(n * goal), due to memoization.
Space Complexity: O(n * goal), for memo storage.
| 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. |
Number of Music Playlists - Leetcode 920 - Python • NeetCodeIO • 14,314 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