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
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).