Skip to main content

920. Number of Music Playlists

hard

Count playlists of length goal from n songs where each song appears at least once and the same song cannot repeat within k slots. A two-axis DP modulo 10^9 + 7.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 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 10^9 + 7.

Constraints

  • 0 <= k < n <= goal <= 100

Examples

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].

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = playlists of length i using exactly j distinct songs. Track distinct count explicitly.

Hint 2

Two transitions: add a new song (j-1 choices already used, n - (j-1) fresh) or repeat an old song (j - k usable repeats if j > k).

Hint 3

Recurrence: dp[i][j] = dp[i-1][j-1] * (n - j + 1) + dp[i-1][j] * max(0, j - k).

Solution approach

Reveal approach

Two-dimensional DP. Define dp[i][j] as the number of valid playlists of length i that use exactly j distinct songs. Two transitions into dp[i][j]: extend a playlist of length i-1 with j-1 distinct songs by playing a brand-new song — there are n - (j - 1) fresh choices — contributing dp[i-1][j-1] * (n - j + 1). Or extend a playlist of length i-1 with j distinct songs by replaying an older one — but only j - k of the j songs can be replayed without violating the k-gap rule — contributing dp[i-1][j] * max(0, j - k). All arithmetic modulo 10^9 + 7. Base case dp[0][0] = 1. Answer is dp[goal][n]. O(goal * n) time, O(goal * n) space (or O(n) with rolling rows).

Complexity

Time
O(goal * n)
Space
O(goal * n)

Related patterns

  • dynamic-programming
  • combinatorics

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Number of Music Playlists and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →