Frontend School

Longest Diverse Sub-Playlist

DSA
medium

Longest Diverse Sub-Playlist

Medium
Arrays
Hashing
Sliding Window

Overview

Spotify is always looking for ways to enhance user experience by recommending diverse content. One aspect of diversity in playlists is the variety of genres. For a given playlist, we want to identify the longest continuous segment (sub-playlist) that features a specific number of unique genres.

This problem challenges your ability to efficiently analyze sequential data, a common task in music streaming platforms, using fundamental data structures and algorithms.

What you need to do / Task

Implement a function longestDiverseSubPlaylist that takes an array of genre IDs (integers) representing a playlist and an integer k, and returns the length of the longest continuous sub-playlist that contains exactly k distinct genre IDs.

Input & output

  • Input:

    • songGenres: An array of integers, where each integer songGenres[i] represents a genre ID of the i-th song in the playlist.
    • k: An integer representing the target number of distinct genre IDs.
  • Output:

    • An integer, the maximum length of a continuous sub-playlist that contains exactly k distinct genre IDs. If no such sub-playlist exists, return 0.

Clarifications

  • A sub-playlist must be continuous (a subarray).
  • If k is 0, an empty sub-playlist has 0 distinct genres. However, the problem asks for the length of the longest such sub-playlist. If k=0, and songGenres is non-empty, no non-empty sub-playlist will have 0 distinct genres. Thus, the longest sub-playlist with 0 distinct genres would be an empty one, returning 0.
  • Genre IDs can be large, but are positive integers.

Examples

1

Example 1

Input:

songGenres = [1,2,1,3,2,4], k = 3

Output:

5

Note:

The sub-playlist [1,2,1,3,2] has genres {1, 2, 3}, which are 3 distinct genres. Its length is 5. Other sub-playlists like [1,2,1,3] (length 4) or [3,2,4] (length 3) also have 3 distinct genres, but 5 is the maximum length.

2

Example 2

Input:

songGenres = [5,5,5,5,5], k = 1

Output:

5

Note:

The entire playlist [5,5,5,5,5] has only 1 distinct genre (genre 5). Its length is 5, which is the maximum possible.

3

Example 3

Input:

songGenres = [1,2,3,4,5], k = 2

Output:

2

Note:

Several sub-playlists have exactly 2 distinct genres, e.g., [1,2], [2,3], [3,4], [4,5]. Each has length 2. This is the maximum.

4

Example 4

Input:

songGenres = [1,2,1,3,2,4], k = 0

Output:

0

Note:

A sub-playlist with 0 distinct genres must be empty. The length of an empty sub-playlist is 0.

5

Example 5

Input:

songGenres = [1,1,2,2], k = 3

Output:

0

Note:

The entire playlist only has 2 distinct genres (1 and 2). It's impossible to form a sub-playlist with exactly 3 distinct genres. So, the result is 0.

Constraints

Constraints & assumptions

  • 1 <= songGenres.length <= 10^5
  • 1 <= songGenres[i] <= 10^9
  • 0 <= k <= songGenres.length

Out of scope

  • Handling invalid input types (e.g., songGenres not an array, k not an integer).
  • Optimizing for extremely sparse genre ID ranges (assume standard hash map performance).

What interviewers evaluate

  • Algorithmic correctness: Does the solution correctly identify the longest sub-playlist for all valid inputs?
  • Efficiency: Is the solution optimal in terms of time and space complexity (aim for O(N) time and O(D) space where D is distinct genres)?
  • Code structure and readability: Is the code well-organized, easy to understand, and maintainable?
  • Edge case handling: Does the solution correctly handle edge cases like k=0, k being larger than total distinct genres, or songGenres containing only one distinct genre?

Loading editor...