LeetCode 920 - Number of Music Playlists

LeetCode Problem 920

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming, Combinatorics

Solution

Problem Understanding

The problem gives us n unique songs and asks us to build playlists of length goal. Songs may repeat, but two important constraints must always hold.

First, every one of the n songs must appear at least once in the playlist. Second, once a song has been played, it cannot be played again until at least k other songs have been played in between.

We are asked to count how many valid playlists exist under these rules. Since the answer can become extremely large, we return it modulo 10^9 + 7.

The input parameters represent the following:

• n is the number of distinct songs available.
• goal is the total length of the playlist.
• k is the repetition restriction distance.

The output is the number of playlists of exactly length goal that use all songs at least once and satisfy the replay restriction.

The constraints are important:

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

Since goal is at most 100, exponential brute-force generation is impossible, but polynomial-time dynamic programming is very feasible. The small upper bound strongly suggests a DP solution with states based on playlist length and song usage counts.

Several edge cases are especially important:

• When k = 0, songs may repeat immediately, so the only requirement is that every song appears at least once.
• When goal = n, every song must appear exactly once because there is no extra room for repetitions.
• When k = n - 1, a song can only repeat after every other song has been played, which creates very strict ordering constraints.
• Small values like n = 1 must still work correctly.
• Repetition counting can easily overflow standard integers, so modulo arithmetic must be applied consistently.

Approaches

Brute Force

A brute-force solution would recursively generate every possible playlist of length goal. At each position, we would try all n songs, check whether replay constraints are satisfied, and verify at the end that every song appeared at least once.

This approach is conceptually simple because it directly models the problem definition. However, its complexity is enormous. In the worst case, there are n^goal possible playlists to examine.

For example, if n = 100 and goal = 100, the search space becomes astronomically large. Even aggressive pruning cannot make this feasible.

Key Insight

The important observation is that the exact order of previously played songs is mostly irrelevant. What really matters is:

• How many positions have already been filled.
• How many unique songs have been used so far.

This naturally leads to dynamic programming.

Suppose we define:

• dp[i][j] as the number of playlists of length i that contain exactly j unique songs.

From this state, there are only two possible transitions:

1. Add a brand new song that has never been used before.
2. Replay an old song that is currently allowed under the k restriction.

This dramatically reduces the state space from exponential to polynomial.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^goal)	O(goal)	Generates every possible playlist recursively
Optimal Dynamic Programming	O(goal × n)	O(goal × n)	Counts playlists using combinational state transitions

Algorithm Walkthrough

Dynamic Programming State

We define:

$$dp[i][j]$$

as the number of playlists of length i that contain exactly j distinct songs.

The final answer will be:

$$dp[goal][n]$$

because we need a playlist of length goal that uses all n songs.

Transition Logic

At every state, we have two choices.

1. Add a New Song

If we currently have j - 1 unique songs and want to reach j unique songs, we can add one new song.

The number of unused songs available is:

$$n - (j - 1)$$

So the transition becomes:

$dp[i][j] += dp[i-1][j-1] \times (n-(j-1))$

This means:

• Build a playlist of length i - 1 with j - 1 unique songs.
• Choose one unused song to append.

2. Replay an Existing Song

We may also replay a previously used song, but only if it is not among the last k played songs.

If we already have j unique songs, then:

• k songs are temporarily blocked.
• j - k songs are eligible for replay.

This transition is:

$dp[i][j] += dp[i-1][j] \times (j-k)$

This transition only applies when j > k.

Base Case

An empty playlist with zero songs used has exactly one valid configuration:

$$dp[0][0] = 1$$

All other states initially start at zero.

Step-by-Step Algorithm

1. Create a 2D DP table of size (goal + 1) × (n + 1) initialized to zero.
2. Set dp[0][0] = 1 because there is exactly one empty playlist.
3. Iterate through playlist lengths from 1 to goal.
4. For each length, iterate through possible counts of unique songs from 1 to n.
5. Compute the contribution from adding a new song:

• Start from dp[i - 1][j - 1]
• Multiply by the number of unused songs.

6. Compute the contribution from replaying an old song:

• Only possible if j > k
• Start from dp[i - 1][j]
• Multiply by the number of reusable songs.

7. Apply modulo 10^9 + 7 after every update.
8. Return dp[goal][n].

Why it works

The DP state completely captures all information needed to continue building valid playlists. At any point, only the playlist length and number of unique songs matter. Every valid playlist extension falls into exactly one of two categories:

• adding a new song
• replaying an existing allowed song

Because the transitions count all valid possibilities without overlap or omission, the DP correctly enumerates every valid playlist exactly once.

Python Solution

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 length in range(1, goal + 1):
            for unique in range(1, n + 1):

                # Add a new song
                dp[length][unique] += (
                    dp[length - 1][unique - 1]
                    * (n - (unique - 1))
                )

                # Replay an old song
                if unique > k:
                    dp[length][unique] += (
                        dp[length - 1][unique]
                        * (unique - k)
                    )

                dp[length][unique] %= MOD

        return dp[goal][n]

The implementation directly follows the DP formulation.

We first create a DP table where rows represent playlist lengths and columns represent how many unique songs have been used.

The base case dp[0][0] = 1 represents the empty playlist.

For each state, we compute two transitions.

The first transition adds a new unused song. If we previously had unique - 1 distinct songs, then there are n - (unique - 1) unused songs remaining.

The second transition reuses an old song. However, only unique - k songs are eligible because the last k songs cannot be replayed immediately.

Modulo arithmetic is applied after every update to prevent integer overflow and satisfy the problem requirement.

Finally, we return dp[goal][n], which represents playlists of full length that use every song at least once.

Go Solution

func numMusicPlaylists(n int, goal int, k int) int {
	const MOD int = 1_000_000_007

	dp := make([][]int, goal+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	dp[0][0] = 1

	for length := 1; length <= goal; length++ {
		for unique := 1; unique <= n; unique++ {

			// Add a new song
			dp[length][unique] +=
				dp[length-1][unique-1] *
					(n - (unique - 1))

			dp[length][unique] %= MOD

			// Replay an old song
			if unique > k {
				dp[length][unique] +=
					dp[length-1][unique] *
						(unique - k)

				dp[length][unique] %= MOD
			}
		}
	}

	return dp[goal][n]
}

The Go implementation mirrors the Python logic closely. Since Go does not automatically resize multidimensional arrays, we explicitly allocate the 2D slice structure.

Modulo operations are performed carefully after each update to avoid overflow growth. Go integers are large enough for intermediate multiplication under these constraints, especially because modulo reduction happens immediately afterward.

Unlike Python, Go does not support negative indexing or dynamic list growth, so the loops and indexing are slightly more explicit.

Worked Examples

Example 1

Input:

n = 3, goal = 3, k = 1

We construct the DP table.

Initial state:

length	unique	value
0	0	1

Length = 1

unique	Calculation	Result
1	dp[0][0] × 3	3

So:

State	Value
dp[1][1]	3

Length = 2

unique	Calculation	Result
1	replay impossible because k=1	0
2	dp[1][1] × 2	6

So:

State	Value
dp[2][2]	6

Length = 3

unique	Calculation	Result
3	dp[2][2] × 1	6

Final answer:

State	Value
dp[3][3]	6

Output:

6

Example 2

Input:

n = 2, goal = 3, k = 0

Since k = 0, songs may repeat immediately.

Length = 1

State	Value
dp[1][1]	2

Length = 2

State	Calculation	Value
dp[2][1]	2 × 1	2
dp[2][2]	2 × 1	2

Length = 3

State	Calculation	Value
dp[3][1]	2 × 1	2
dp[3][2]	(2 × 1) + (2 × 2)	6

Final answer:

6

Example 3

Input:

n = 2, goal = 3, k = 1

Songs cannot repeat immediately.

Length = 1

State	Value
dp[1][1]	2

Length = 2

State	Value
dp[2][2]	2

Length = 3

Replay becomes possible because one different song separates repeats.

State	Calculation	Value
dp[3][2]	2 × 1	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(goal × n)	Each DP state is computed once
Space	O(goal × n)	DP table stores all states

The algorithm iterates through every combination of playlist length and unique song count exactly once. Each state performs only constant-time work, so the total runtime is proportional to the number of states.

The space complexity comes from storing the full DP table. Since both goal and n are at most 100, this is extremely manageable.

Test Cases

sol = Solution()

# Provided examples
assert sol.numMusicPlaylists(3, 3, 1) == 6  # all songs exactly once
assert sol.numMusicPlaylists(2, 3, 0) == 6  # immediate repeats allowed
assert sol.numMusicPlaylists(2, 3, 1) == 2  # repeat requires separation

# Smallest valid input
assert sol.numMusicPlaylists(1, 1, 0) == 1  # single song once

# Single song repeated
assert sol.numMusicPlaylists(1, 5, 0) == 1  # only one possible playlist

# goal equals n
assert sol.numMusicPlaylists(4, 4, 2) == 24  # all permutations

# Large k restriction
assert sol.numMusicPlaylists(3, 5, 2) == 6  # strict replay spacing

# Repeats heavily used
assert sol.numMusicPlaylists(3, 6, 0) == 540  # many reuse possibilities

# No valid replay until all songs used
assert sol.numMusicPlaylists(5, 5, 4) == 120  # factorial permutations

# Stress-style medium case
assert sol.numMusicPlaylists(10, 15, 3) > 0  # verifies larger DP states

print("All tests passed.")

Test	Why
(3,3,1)	Basic permutation scenario
(2,3,0)	Immediate repetition allowed
(2,3,1)	Enforces replay separation
(1,1,0)	Smallest valid input
(1,5,0)	Single repeated song
(4,4,2)	Every song used exactly once
(3,5,2)	Very strict replay constraints
(3,6,0)	Heavy reuse scenario
(5,5,4)	Maximum replay restriction
(10,15,3)	Medium-sized stress test

Edge Cases

Case 1: k = 0

When k is zero, songs may repeat immediately. This changes the replay logic significantly because every previously used song is always eligible for reuse.

A buggy implementation might accidentally forbid immediate repetition even when k = 0. Our implementation handles this correctly because the replay transition uses unique - k, which becomes unique.

Case 2: goal = n

When the playlist length exactly equals the number of distinct songs, every song must appear exactly once. No repetitions are possible.

In this scenario, the answer should simply count permutations of the songs. The DP naturally handles this because replay transitions never contribute meaningfully before all songs are used.

Case 3: k = n - 1

This is the strictest possible replay restriction. A song cannot repeat until every other song has been played.

This edge case is easy to mishandle because the number of reusable songs becomes extremely small. Our transition condition if unique > k guarantees that replay only occurs when enough distinct songs exist to satisfy the spacing rule.

Case 4: Single Song Input

When n = 1, there is only one possible song. If k = 0, the playlist is uniquely determined regardless of goal.

Implementations that assume multiple songs exist may incorrectly compute replay counts or access invalid DP states. Our DP formulation works naturally even for this minimal configuration.