LeetCode 920: Number of Music Playlists

Problem Restatement

We have n different songs.

We need to create a playlist of length goal.

The playlist must satisfy two rules:

Return the number of valid playlists modulo:

10**9 + 7

The official problem asks for the number of possible playlists given n, goal, and k.

Input and Output

Function shape:

def numMusicPlaylists(n: int, goal: int, k: int) -> int:
    ...

Examples

Example 1:

n = 3
goal = 3
k = 1

We need a playlist of length 3 using all 3 songs.

Since the playlist length equals the number of songs, each song appears exactly once.

Valid playlists:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Answer:

6

Example 2:

n = 2
goal = 3
k = 0

Both songs must appear at least once.

Since k = 0, a song can repeat immediately.

Valid playlists:

[1, 1, 2]
[1, 2, 1]
[2, 1, 2]
[2, 2, 1]

Answer:

4

Example 3:

n = 2
goal = 3
k = 1

A song cannot repeat until at least one other song has played.

Valid playlists:

[1, 2, 1]
[2, 1, 2]

Answer:

2

First Thought: Generate Every Playlist

A direct method is to generate every possible playlist of length goal.

Each position has n choices, so there are:

n ** goal

possible playlists.

For each playlist, we could check:

1. Whether every song appears.
2. Whether every repeated song respects the k rule.

This is too slow.

We need to count valid playlists without enumerating them.

Key Insight

Build the playlist one position at a time.

At any point, we only need to know:

1. The current playlist length.
2. How many distinct songs have already been used.

Let:

dp[i][j]

mean:

The number of playlists of length i that use exactly j distinct songs.

There are two ways to extend such a playlist.

Transition 1: Add a New Song

If the playlist currently uses j - 1 distinct songs, then we can add a new song as the next song.

There are:

n - (j - 1)

unused songs available.

So:

dp[i][j] += dp[i - 1][j - 1] * (n - j + 1)

Transition 2: Replay an Old Song

If the playlist already uses j distinct songs, we may replay one of them.

But the last k different songs are blocked from replay.

So the number of replayable songs is:

j - k

if j > k.

Thus:

dp[i][j] += dp[i - 1][j] * (j - k)

This is the standard DP recurrence for this problem.

Algorithm

1. Create a DP table with (goal + 1) rows and (n + 1) columns.
2. Set:

dp[0][0] = 1

There is one way to create an empty playlist with zero songs used.

3. For each playlist length i from 1 to goal:
   • For each distinct song count j from 1 to n:
     • Add ways that place a new song.
     • Add ways that replay an old allowed song.
4. Return:

dp[goal][n]

because the final playlist must have length goal and use all n songs.

Correctness

The DP state dp[i][j] counts playlists of length i that use exactly j distinct songs.

Every valid playlist of length i with j distinct songs ends in exactly one of two ways.

The last song is new. Then the first i - 1 songs used exactly j - 1 distinct songs, and there are n - j + 1 choices for the new song.

Or the last song was already used before. Then the first i - 1 songs already used exactly j distinct songs, and only j - k of those songs are legal to replay because the most recent k different songs are blocked.

These two cases are disjoint and cover all possible valid endings.

The recurrence therefore counts every valid playlist exactly once.

The base case dp[0][0] = 1 is correct because there is exactly one empty playlist.

At the end, dp[goal][n] counts playlists of the required length that use all songs at least once.

Therefore, the algorithm returns the required number.

Complexity

Implementation

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        MOD = 10**9 + 7

        dp = [[0] * (n + 1) for _ in range(goal + 1)]
        dp[0][0] = 1

        for i in range(1, goal + 1):
            for j in range(1, n + 1):
                add_new = dp[i - 1][j - 1] * (n - j + 1)

                replay_old = 0
                if j > k:
                    replay_old = dp[i - 1][j] * (j - k)

                dp[i][j] = (add_new + replay_old) % MOD

        return dp[goal][n]

Code Explanation

Create the modulo constant:

MOD = 10**9 + 7

Create the DP table:

dp = [[0] * (n + 1) for _ in range(goal + 1)]

The empty playlist base case is:

dp[0][0] = 1

For each length and distinct-song count:

for i in range(1, goal + 1):
    for j in range(1, n + 1):

Count ways to add a song that has never appeared before:

add_new = dp[i - 1][j - 1] * (n - j + 1)

Count ways to replay an old song:

if j > k:
    replay_old = dp[i - 1][j] * (j - k)

Combine both cases:

dp[i][j] = (add_new + replay_old) % MOD

The answer must use all n songs:

return dp[goal][n]

Testing

def run_tests():
    s = Solution()

    assert s.numMusicPlaylists(3, 3, 1) == 6
    assert s.numMusicPlaylists(2, 3, 0) == 4
    assert s.numMusicPlaylists(2, 3, 1) == 2
    assert s.numMusicPlaylists(1, 1, 0) == 1
    assert s.numMusicPlaylists(3, 4, 1) == 18
    assert s.numMusicPlaylists(3, 5, 2) == 6

    print("all tests passed")

run_tests()

Test meaning: