LeetCode Entry

920. Number of Music Playlists

06.08.2023 hard 2023 kotlin

Playlists number playing n songs goal times, repeating each once in a k times

920. Number of Music Playlists hard blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/300

Problem TLDR

Playlists number playing n songs goal times, repeating each once in a k times

Intuition

We can search through the problem space, taking each new song with the given rules: song can be repeated only after another k song got played. When we have the goal songs, check if all distinct songs are played.

We can cache the solution by curr and used map, but that will give TLE.

The hard trick here is that the result only depends on how many distinct songs are played.

Approach

Use DFS and memo.

Complexity

  • Time complexity: \(O(n^2)\)

  • Space complexity: \(O(n^2)\)

Code


    fun numMusicPlaylists(n: Int, goal: Int, k: Int): Int {
        val cache = mutableMapOf<Pair<Int, Int>, Long>()
        fun dfs(curr: Int, used: Map<Int, Int>): Long = cache.getOrPut(curr to used.size) {
          if (curr > goal) {
            if ((1..n).all { used.contains(it) }) 1L else 0L
          } else (1..n).asSequence().map { i ->
              if (curr <= used[i] ?: 0) 0L else
                dfs(curr + 1, used.toMutableMap().apply { this[i] = curr + k })
            }.sum()!! % 1_000_000_007L
        }
        return dfs(1, mapOf()).toInt()
    }