You have access to ranked lists of songs for various users. Each song is represented as an integer, and more preferred songs appear earlier in each list. For example, the list [4, 1, 7] indicates that a user likes song 4 the best, followed by songs 1 and 7.
Given a set of these ranked lists, interleave them to create a playlist that satisfies everyone’s priorities.
For example, suppose your input is {[1, 7, 3], [2, 1, 6, 7, 9], [3, 9, 5]}. In this case a satisfactory playlist could be [2, 1, 6, 7, 3, 9, 5].
Input: [[1,7,3],[2,1,6,7,9],[3,9,5]]Output: [2,1,6,7,3,9,5]Explanation: This playlist respects all user preferences - each user's songs appear in their preferred relative order.
Input: [[1,2,3],[3,2,1]]Output: [1,3,2]Explanation: Song 1 must come before 2 and 3(from first list), song 3 must come before 2 and 1(from second list). One valid ordering is[1,3,2].
This problem is essentially asking for a topological ordering that respects multiple partial orderings. Each user’s ranked list defines a partial order (song A must come before song B if A appears before B in their list). We can model this as a directed acyclic graph (DAG) where edges represent “comes before” relationships, then find a topological ordering.
classSolution:
defcreatePlaylist(self, lists: List[List[int]]) -> List[int]:
allSongs = set()
graph = defaultdict(set)
inDegree = defaultdict(int)
# Collect all songs and initialize in-degreefor lst in lists:
for song in lst:
allSongs.add(song)
inDegree[song] = inDegree.get(song, 0)
# Build graph and calculate in-degreesfor lst in lists:
for i in range(len(lst)):
for j in range(i +1, len(lst)):
from_song, to_song = lst[i], lst[j]
if to_song notin graph[from_song]:
graph[from_song].add(to_song)
inDegree[to_song] +=1# Kahn's algorithm queue = deque([song for song in inDegree if inDegree[song] ==0])
ans = []
while queue:
curr = queue.popleft()
ans.append(curr)
for next_song in graph[curr]:
inDegree[next_song] -=1if inDegree[next_song] ==0:
queue.append(next_song)
return ans
⏰ Time complexity: O(N + E), where N is the total number of unique songs and E is the total number of ordering relationships. Building the graph takes O(S²L) where S is average songs per list and L is number of lists, and topological sort takes O(N + E).
🧺 Space complexity: O(N + E), for storing the graph, in-degree map, and queue.
Instead of building a full graph, we can think of this as merging multiple sorted lists while maintaining the relative order within each list. We use a priority-based approach where we track the position of each song in each user’s list and always pick the song that appears earliest in any remaining list.
classSolution:
defcreatePlaylist(self, lists: List[List[int]]) -> List[int]:
allSongs = set()
for lst in lists:
allSongs.update(lst)
ans = []
pointers = [0] * len(lists)
used = set()
while len(ans) < len(allSongs):
priorities = {}
# Calculate priority for each available songfor i, lst in enumerate(lists):
for j in range(pointers[i], len(lst)):
song = lst[j]
if song notin used:
priorities[song] = min(priorities.get(song, float('inf')), j)
# Find song with highest priority (lowest position) nextSong = min(priorities.keys(), key=lambda x: priorities[x])
ans.append(nextSong)
used.add(nextSong)
# Update pointersfor i in range(len(lists)):
while pointers[i] < len(lists[i]) and lists[i][pointers[i]] in used:
pointers[i] +=1return ans
⏰ Time complexity: O(N² × L × S), where N is number of unique songs, L is number of lists, and S is average songs per list. For each of N iterations, we scan all remaining songs across all lists.
🧺 Space complexity: O(N), for storing the result, used set, and priority map.