23. Merge k Sorted Lists

How to solve Merge k Sorted Lists (LeetCode 23): the approach in brief

The problem

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Pattern

Merge k Sorted Lists is a Heap (Priority Queue) Patterns problem, in the K-way Merge subpattern. The pattern covers top K elements, K-way merge, two heaps for median, and scheduling

Master K-way merge pattern using min heap. Merge k sorted lists and find kth smallest in matrix.

Approach outline

1. Consider how to efficiently merge multiple sorted lists into one sorted list using an appropriate data structure.
2. Think about a data structure that can quickly provide the smallest element among multiple candidates at each step.
3. Using a min-heap (priority queue) to keep track of the smallest current elements from each list can help efficiently determine the next node to add.

Complexity

The reference solution runs in O(N log k) time and O(k) space.

Asked at

Merge k Sorted Lists has been reported in interviews at Amazon, Facebook, Microsoft, Bloomberg, Apple, Oracle, Databricks, Google.