23. Merge k Sorted Lists
Merge k Sorted Lists (LeetCode 23) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the K-way Merge subpattern.
- Blind 75 · #24 of 75 · Linked List
- NeetCode 150 · #44 of 150 · Linked List
- NeetCode 250 · #86 of 250 · Linked List
How to solve Merge k Sorted Lists
Merge k Sorted Lists is a K-way Merge Using Heap problem, part of Heap (Priority Queue) Patterns. Master K-way merge pattern using min heap. Merge k sorted lists and find kth smallest in matrix.
Work towards the solution in these steps:
- Consider how to efficiently merge multiple sorted lists into one sorted list using an appropriate data structure.
- Think about a data structure that can quickly provide the smallest element among multiple candidates at each step.
- 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.
The reference solution runs in O(N log k) time and O(k) space.
The Merge k Sorted Lists solution and editorial walks through the full approach with reference code.
Problem statement
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6
Example 2:
Input: lists = [] Output: []
Example 3:
Input: lists = [[]] Output: []
Constraints:
- k == lists.length
- 0 <= k <= 104
- 0 <= lists[i].length <= 500
- -104 <= lists[i][j] <= 104
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 104.
Topics and companies
Topics: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort.
Reported in interviews at Amazon, Facebook, Microsoft, Bloomberg, Apple, Oracle, Databricks, Google, Twitter, Uber, Adobe, Wish and others.
How to practise Merge k Sorted Lists on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N log k) time and O(k) space.
Open Merge k Sorted Lists in the code editor, or read the Merge k Sorted Lists editorial for a worked solution with its approach and complexity analysis.
Where Merge k Sorted Lists sits in the DSA pattern sheet
Problems related to Merge k Sorted Lists
Other problems that use the same K-way Merge and Heap (Priority Queue) Patterns techniques:
- Design Twitter — Medium, same subpattern
- Find K Pairs with Smallest Sums — Medium, same subpattern
- Kth Smallest Element in a Sorted Matrix — Medium, same subpattern
- Smallest Range Covering Elements from K Lists — Hard, same subpattern
- Finding MK Average — Hard, same pattern
- Find Median from Data Stream — Hard, same pattern
Merge k Sorted Lists FAQ
What is the LeetCode number of Merge k Sorted Lists?
Merge k Sorted Lists is LeetCode problem 23, rated Hard.
What pattern is used to solve Merge k Sorted Lists?
Merge k Sorted Lists is a K-way Merge Using Heap problem. It belongs to the Heap (Priority Queue) Patterns pattern, in the K-way Merge subpattern.
What is the time complexity of Merge k Sorted Lists?
The reference solution runs in O(N log k) time and O(k) space.
Which companies ask Merge k Sorted Lists?
Merge k Sorted Lists has been reported in interviews at Amazon, Facebook, Microsoft, Bloomberg, Apple, Oracle, Databricks, Google, Twitter, Uber, Adobe, Wish and others.