Pro

920. Number of Music Playlists - Explanation

Problem Link



Prerequisites

Before attempting this problem, you should be comfortable with:

  • Dynamic Programming - Both top-down (memoization) and bottom-up tabulation approaches
  • Combinatorics - Understanding how to count arrangements with constraints (permutations with restrictions)
  • Modular Arithmetic - Performing operations under modulo to handle large numbers without overflow
  • State Space Design - Defining DP states with multiple dimensions (playlist length and distinct songs used)

1. Dynamic Programming (Top-Down)

Intuition

We need to count valid playlists of exactly goal songs using exactly n different songs, where a song can only repeat after k other songs have played. At each position in the playlist, we have two choices: add a new song we have not used yet, or replay an old song (if enough songs have been played since its last appearance). The number of ways to add a new song depends on how many songs we have already used, and the number of ways to replay an old song depends on how many songs are eligible for replay.

Algorithm

  1. Define a recursive function count(cur_goal, old_songs) where cur_goal is the remaining playlist slots and old_songs is the number of distinct songs used so far.
  2. Base cases:
    • If cur_goal == 0 and old_songs == n, we have a valid playlist, return 1.
    • If cur_goal == 0 or old_songs > n, this path is invalid, return 0.
  3. Recursive transitions:
    • Add a new song: there are (n - old_songs) new songs available, and this leads to count(cur_goal - 1, old_songs + 1).
    • Replay an old song: if old_songs > k, there are (old_songs - k) songs eligible for replay, leading to count(cur_goal - 1, old_songs).
  4. Memoize results to avoid recomputation.
  5. Return count(goal, 0) as the final answer, modulo 10^9 + 7.
class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        mod = 10**9 + 7
        dp = {}

        def count(cur_goal, old_songs):
            if cur_goal == 0 and old_songs == n:
                return 1
            if cur_goal == 0 or old_songs > n:
                return 0
            if (cur_goal, old_songs) in dp:
                return dp[(cur_goal, old_songs)]

            res = (n - old_songs) * count(cur_goal - 1, old_songs + 1)
            if old_songs > k:
                res += (old_songs - k) * count(cur_goal - 1, old_songs)
            dp[(cur_goal, old_songs)] = res % mod
            return dp[(cur_goal, old_songs)]

        return count(goal, 0)

Time & Space Complexity

  • Time complexity: O(g∗n)O(g * n)
  • Space complexity: O(g∗n)O(g * n)

Where gg is the number of songs to listen and nn is the number of different songs.

2. Dynamic Programming (Bottom-Up)

Intuition

The top-down solution can be converted to a bottom-up approach by iterating through all possible states. We build a 2D table where dp[i][j] represents the number of ways to create a playlist of length i using exactly j distinct songs. We fill this table row by row, starting from the base case and building up to our target state.

Algorithm

  1. Create a 2D array dp[goal+1][n+1] initialized to 0, with dp[0][0] = 1 as the base case (empty playlist with no songs used).
  2. For each playlist length cur_goal from 1 to goal:
    • For each count of distinct songs old_songs from 1 to n:
      • Add a new song: multiply dp[cur_goal - 1][old_songs - 1] by (n - old_songs + 1).
      • Replay an old song (if old_songs > k): add dp[cur_goal - 1][old_songs] * (old_songs - k).
      • Store the sum in dp[cur_goal][old_songs], taking modulo 10^9 + 7.
  3. Return dp[goal][n].
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 cur_goal in range(1, goal + 1):
            for old_songs in range(1, n + 1):
                res = (dp[cur_goal - 1][old_songs - 1] * (n - old_songs + 1)) % mod
                if old_songs > k:
                    res = (res + dp[cur_goal - 1][old_songs] * (old_songs - k)) % mod
                dp[cur_goal][old_songs] = res

        return dp[goal][n]

Time & Space Complexity

  • Time complexity: O(g∗n)O(g * n)
  • Space complexity: O(g∗n)O(g * n)

Where gg is the number of songs to listen and nn is the number of different songs.

3. Dynamic Programming (Space Optimized)

Intuition

Looking at the bottom-up recurrence, each row only depends on the previous row. This means we do not need to store the entire 2D table. Instead, we can use a single 1D array and update it in place, being careful to preserve the previous row's values where needed. This reduces space from O(goal * n) to O(n).

Algorithm

  1. Create a 1D array dp[n+1] initialized to 0.
  2. For each playlist length cur_goal from 1 to goal:
    • Track prev to store the value from the previous row that we need before overwriting.
    • Initialize prev = 1 when cur_goal == 1 (base case for adding the first song), otherwise prev = 0.
    • For each count of distinct songs old_songs from 1 to n:
      • Compute the new value using prev (for adding a new song) and dp[old_songs] (for replaying an old song).
      • Update prev to the old value of dp[old_songs] before overwriting.
      • Store the result in dp[old_songs].
  3. Return dp[n].
class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        mod = 10**9 + 7
        dp = [0] * (n + 1)

        for cur_goal in range(1, goal + 1):
            prev = 1 if cur_goal == 1 else 0
            for old_songs in range(1, n + 1):
                res = (prev * (n - old_songs + 1)) % mod
                if old_songs > k:
                    res = (res + dp[old_songs] * (old_songs - k)) % mod
                prev = dp[old_songs]
                dp[old_songs] = res

        return dp[n]

Time & Space Complexity

  • Time complexity: O(g∗n)O(g * n)
  • Space complexity: O(n)O(n)

Where gg is the number of songs to listen and nn is the number of different songs.

Common Pitfalls

Forgetting the Gap Constraint for Replaying Songs

A song can only be replayed after k other songs have been played. This means with old_songs distinct songs used, only old_songs - k are eligible for replay (if old_songs > k). Forgetting this constraint or using old_songs directly leads to overcounting.

Integer Overflow in Modular Arithmetic

Multiplying two values before taking the modulo can overflow 32-bit integers. Always cast to long or long long before multiplication, then apply modulo. For example, (n - oldSongs) * count can overflow if not handled properly.

Incorrect Base Case Definition

The base case should be dp[0][0] = 1 (one way to have an empty playlist with zero songs used). Setting dp[0][n] = 1 or other incorrect initializations will propagate errors through all subsequent states.

Confusing State Dimensions

The DP state tracks (playlist_length, distinct_songs_used). Confusing which dimension is which, or iterating in the wrong order, leads to accessing uncomputed states or incorrect transitions. In bottom-up, iterate playlist length in the outer loop and distinct songs in the inner loop.

Not Requiring Exactly N Distinct Songs

The final answer must use exactly n distinct songs. A common error is returning dp[goal][any] summed over all possible song counts, when it should specifically be dp[goal][n].