Practice/Spotify/Most Played Songs

Most Played Songs

CodingMust

Problem

You are building a music streaming analytics feature that generates personalized playlists. Given a list of song titles representing a user's listening history and an integer k, return the k most frequently played songs. The songs should be ordered by play count from highest to lowest. If multiple songs have the same play count, you may return them in any order.

Requirements

1. Accept a list of song titles (strings) and an integer k as input
2. Count the frequency of each song in the listening history
3. Return the k songs with the highest play counts
4. Order the result by frequency (descending)
5. If there are ties in play count, any valid ordering of those tied songs is acceptable

Constraints

• 1 ≤ k ≤ number of unique songs
• 1 ≤ songs.length ≤ 10⁵
• Each song title is a non-empty string
• Song titles are case-sensitive
• The time complexity should be better than O(n log n) where n is the total number of songs

Examples

Example 1:

Input: songs = ["Yesterday", "Let It Be", "Yesterday", "Hey Jude", "Let It Be", "Yesterday"], k = 2 Output: ["Yesterday", "Let It Be"] Explanation: "Yesterday" appears 3 times and "Let It Be" appears 2 times, making them the top 2 songs.

Example 2:

Input: songs = ["Song1", "Song2", "Song3"], k = 1 Output: ["Song1"] Explanation: All songs appear once, so any of them can be returned. We return the first one encountered.

Example 3:

Input: songs = ["Pop", "Rock", "Pop", "Jazz", "Rock", "Pop"], k = 3 Output: ["Pop", "Rock", "Jazz"] Explanation: "Pop" appears 3 times, "Rock" appears 2 times, and "Jazz" appears 1 time.