Implement and Analyze 'Merge k Sorted Lists' Algorithm
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
Algorithm coding challenge during the final interview round.
##### Question
Implement LeetCode 23 ‘Merge k Sorted Lists’ and explain your complexity analysis.
##### Hints
Compare heap vs divide-and-conquer solutions.
Quick Answer: This question evaluates algorithm design skills and complexity analysis for merging multiple sorted sequences, measuring proficiency with appropriate data structures, time-space trade-offs, and correctness reasoning.
You are given k sorted linked lists represented as arrays of integers. Merge all the lists into one sorted array and return it.
Constraints
- 0 <= k <= 10^4
- 0 <= length of each list <= 10^5
- Sum of lengths across all lists N <= 2 * 10^5
- -10^9 <= value <= 10^9
- Each input list is sorted in non-decreasing order
Solution
from typing import List, Tuple
import heapq
def merge_k_sorted_lists(lists: List[List[int]]) -> List[int]:
# Min-heap of tuples: (value, list_index, index_in_list)
heap: List[Tuple[int, int, int]] = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
result: List[int] = []
while heap:
val, li, idx = heapq.heappop(heap)
result.append(val)
next_idx = idx + 1
if next_idx < len(lists[li]):
heapq.heappush(heap, (lists[li][next_idx], li, next_idx))
return result
Explanation
Initialize a min-heap with the first element of each non-empty list. Repeatedly pop the smallest element and append it to the result. When popping (v, i, j), push the next element from the same list i (if it exists). This ensures at most one element from each list is in the heap at a time, maintaining a heap size up to k. This approach is optimal for k-way merging.
Time complexity: O(N log k), where N is the total number of elements across all lists. Space complexity: O(k) auxiliary space for the heap (excluding the output array).
Hints
- Use a min-heap that stores (value, list_index, index_in_list). Initialize it with the first element of each non-empty list.
- Each pop yields the next smallest value; push the next element from the same list.
- An alternative is divide-and-conquer pairwise merging, which also achieves O(N log k).