Problem Link - Practice - Music Player
Problem Statement:
The functionality of a playlist queue needs to be implemented, i.e., adding a song to the queue, playing the next song, playing the previous song, switching to a song, etc.
Approach:
The key idea of this solution is to use a doubly linked list to manage the songs in the music player. Each song is represented by a node that contains the song ID and pointers to the previous and next songs. This structure allows for easy navigation between songs.
Here’s a breakdown of the approach:
-
MusicPlayer Class:
- head: A pointer to the first song in the list.
- currentSong: A pointer to the song currently being played.
-
addSong(
int songId):- This function creates a new song node and adds it to the end of the list.
- If the list is empty, the new song becomes both the head and the current song.
- Otherwise, it traverses to the end of the list and links the new song.
-
playNext():
- Moves the current song pointer to the next song, if available.
-
playPrev():
- Moves the current song pointer to the previous song, if available.
-
switchSong(
int songId):- This function allows switching to a specific song by traversing the list until the song ID matches.
-
current():
- Returns the song ID of the song currently being played.
Time Complexity:
-
addSong: O(n) in the worst case, where n is the number of songs (traversing to the end).
-
playNext and playPrev: O(1) since they simply move the pointer.
-
switchSong: O(n) in the worst case, as it may need to traverse the entire list.
-
current: O(1) since it directly returns the current song’s ID.
Space Complexity:
- O(n) because we store n nodes in the linked list, with each node representing a song.