Frontend School

Shortest Balanced Playlist Segment

DSA
hard

Shortest Balanced Playlist Segment

Hard
Sliding Window
Hash Map
Arrays

Overview

At Spotify, we're constantly striving to enhance the listening experience through intelligent playlist curation. A key aspect of a high-quality playlist is its 'balance' — ensuring a diverse selection of music while keeping segments concise and focused. For our automated playlist generation system, we need to identify optimal sub-segments that meet specific criteria.

This problem challenges you to find the shortest continuous segment within a given playlist that satisfies both a minimum genre diversity and a maximum total duration constraint. This helps in creating 'mini-mixes' or dynamic transitions within larger playlists.

What you need to do / Task

Your task is to implement a function shortestBalancedPlaylistSegment that takes a playlist (an array of Track objects), a minimum number of distinct genres, and a maximum total duration. The function should return the length of the shortest contiguous sub-segment of tracks that meets both of the following conditions:

  1. The sub-segment contains at least minDistinctGenres unique genres.
  2. The total combined duration of tracks within the sub-segment is at most maxTotalDuration.

If no such sub-segment exists in the playlist, return -1.

Input & output

Input:

  • tracks: An array of Track objects. Each Track object has two properties:
    • genre: A string representing the music genre (e.g., "pop", "rock", "jazz").
    • duration: A number representing the track's duration in seconds.
  • minDistinctGenres: A number representing the minimum required count of distinct genres in the segment.
  • maxTotalDuration: A number representing the maximum allowed total duration of the segment.

Output:

  • A number representing the length (number of tracks) of the shortest valid sub-segment. Return -1 if no such segment exists.

Clarifications

  • An empty tracks array will not be provided as input (see constraints).
  • If minDistinctGenres is 1, any single track itself (if its duration is within maxTotalDuration) forms a valid segment of length 1.
  • A genre is considered distinct if its string value is unique within the segment.

Examples

1

Example 1

Input:

tracks = [{"genre": "pop", "duration": 10}, {"genre": "rock", "duration": 5}, {"genre": "pop", "duration": 8}, {"genre": "jazz", "duration": 12}], minDistinctGenres = 2, maxTotalDuration = 20

Output:

2

Note:

The segment [{ genre: "rock", duration: 5 }, { genre: "pop", duration: 8 }] has 2 distinct genres ("rock", "pop") and total duration 13 <= 20. Its length is 2. The segment [{ genre: "pop", duration: 8 }, { genre: "jazz", duration: 12 }] also has 2 distinct genres ("pop", "jazz") and total duration 20 <= 20. Its length is 2. This is the shortest possible.

2

Example 2

Input:

tracks = [{"genre": "pop", "duration": 100}, {"genre": "rock", "duration": 100}], minDistinctGenres = 2, maxTotalDuration = 50

Output:

-1

Note:

Any segment containing 2 distinct genres (e.g., the whole playlist) would have a total duration of 200, which exceeds maxTotalDuration = 50. No single genre segment satisfies minDistinctGenres = 2. Thus, no valid segment exists.

3

Example 3

Input:

tracks = [{"genre": "A", "duration": 1}, {"genre": "B", "duration": 1}, {"genre": "C", "duration": 1}, {"genre": "A", "duration": 10}, {"genre": "D", "duration": 1}], minDistinctGenres = 3, maxTotalDuration = 5

Output:

3

Note:

The segment [{ genre: "A", duration: 1 }, { genre: "B", duration: 1 }, { genre: "C", duration: 1 }] has 3 distinct genres and total duration 3 <= 5. Its length is 3. Other segments like [{ genre: "B", duration: 1 }, { genre: "C", duration: 1 }, { genre: "A", duration: 10 }] have 3 distinct genres but duration 12 > 5. No shorter segment satisfies both conditions.

Constraints

Constraints & assumptions

  • 1 <= tracks.length <= 10^5
  • Each track.genre is a string with length between 1 and 20, consisting of lowercase English letters.
  • Each track.duration is an integer between 1 and 10^9.
  • 1 <= minDistinctGenres <= tracks.length
  • 1 <= maxTotalDuration <= 10^14 (The sum of durations can be large, but fits within standard 64-bit floating-point numbers used by JavaScript's number type without precision loss for integers up to 2^53 - 1).

What interviewers evaluate

  • Algorithmic Approach: Ability to correctly identify and implement an efficient sliding window algorithm.
  • Constraint Handling: Skill in managing multiple, interdependent constraints (distinct genre count and total duration) simultaneously.
  • Data Structure Usage: Effective use of data structures (e.g., hash maps) to track window state efficiently.
  • Edge Cases & Correctness: Proper handling of edge cases, such as an empty result or single-element segments, ensuring overall correctness.
  • Code Quality: Writing clean, readable, and maintainable code with appropriate variable names and comments.

Loading editor...