Heap
Merge K Sorted Lists
DESCRIPTION (inspired by Leetcode.com)
Given k linked lists, each sorted in ascending order, in a list lists, write a function to merge the input lists into one sorted linked list.
Example 1:
Inputs:
lists = [[3,4,6],[2,3,5],[-1,6]] 3 -> 4 -> 6 2 -> 3 -> 5 -1 -> 6
Output:
[-1,2,3,3,4,5,6,6]
-1 -> 2 -> 3 -> 3 -> 4 -> 5 -> 6 -> 6
// class ListNode {
// int val;
// ListNode next;
// }
public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
// Your code goes here
}
}Run your code to see results here
Have suggestions or found something wrong?
Explanation
This problem can be solved using a min-heap of size k.
The min-heap will always store the next unmerged element from each of the k sorted arrays. The element with the smallest value sits at the root of the heap. We build the merged array by repeatedly popping the root from the heap. Each time we pop from the heap, we also push the next element from the same array (if one exists) onto the heap.
When the heap is empty, all elements from all arrays have been merged, and we can return the merged result.
Step 1: Initialize the heap
The first step is to initialize the heap with the first element from each of the k arrays. We iterate over each array and push a tuple containing three values onto the heap:
- The element's value
- The array's index (which array it came from)
- The element's index within that array (starting at 0)
public ListNode mergeKLists(List<ListNode> lists) {if (lists == null || lists.isEmpty()) {return null;}List<ListNode> nonEmpty = new ArrayList<>();for (ListNode head : lists) {if (head != null) {nonEmpty.add(head);}}if (nonEmpty.isEmpty()) {return null;}PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));for (ListNode head : nonEmpty) {heap.offer(head);}ListNode dummy = new ListNode(0);ListNode current = dummy;while (!heap.isEmpty()) {ListNode node = heap.poll();current.next = node;current = current.next;if (node.next != null) {heap.offer(node.next);}}return dummy.next;}
initialize heap
0 / 3
Step 2: Build the merged array
With the heap initialized, we can now build the merged result array. We start by creating an empty result array where we'll append elements in sorted order.
public ListNode mergeKLists(List<ListNode> lists) {if (lists == null || lists.isEmpty()) {return null;}List<ListNode> nonEmpty = new ArrayList<>();for (ListNode head : lists) {if (head != null) {nonEmpty.add(head);}}if (nonEmpty.isEmpty()) {return null;}PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));for (ListNode head : nonEmpty) {heap.offer(head);}ListNode dummy = new ListNode(0);ListNode current = dummy;while (!heap.isEmpty()) {ListNode node = heap.poll();current.next = node;current = current.next;if (node.next != null) {heap.offer(node.next);}}return dummy.next;}
add -1 to heap
0 / 1
Now, we repeatedly pop the root of the heap, which gives us the element with the smallest value among the unmerged elements from the k arrays. We append this value to our result array.
public ListNode mergeKLists(List<ListNode> lists) {if (lists == null || lists.isEmpty()) {return null;}List<ListNode> nonEmpty = new ArrayList<>();for (ListNode head : lists) {if (head != null) {nonEmpty.add(head);}}if (nonEmpty.isEmpty()) {return null;}PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));for (ListNode head : nonEmpty) {heap.offer(head);}ListNode dummy = new ListNode(0);ListNode current = dummy;while (!heap.isEmpty()) {ListNode node = heap.poll();current.next = node;current = current.next;if (node.next != null) {heap.offer(node.next);}}return dummy.next;}
initialize result array
0 / 1
To ensure that our heap always contains the next unmerged element from each array, after popping an element, we check if there's a next element in the same array. If there is, we push a tuple with the next element's value, the same array index, and the incremented element index onto the heap.
public ListNode mergeKLists(List<ListNode> lists) {if (lists == null || lists.isEmpty()) {return null;}List<ListNode> nonEmpty = new ArrayList<>();for (ListNode head : lists) {if (head != null) {nonEmpty.add(head);}}if (nonEmpty.isEmpty()) {return null;}PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));for (ListNode head : nonEmpty) {heap.offer(head);}ListNode dummy = new ListNode(0);ListNode current = dummy;while (!heap.isEmpty()) {ListNode node = heap.poll();current.next = node;current = current.next;if (node.next != null) {heap.offer(node.next);}}return dummy.next;}
add -1 to result
0 / 1
When the heap is empty, all elements from all arrays have been merged, and we can return the result array.
public ListNode mergeKLists(List<ListNode> lists) {if (lists == null || lists.isEmpty()) {return null;}List<ListNode> nonEmpty = new ArrayList<>();for (ListNode head : lists) {if (head != null) {nonEmpty.add(head);}}if (nonEmpty.isEmpty()) {return null;}PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));for (ListNode head : nonEmpty) {heap.offer(head);}ListNode dummy = new ListNode(0);ListNode current = dummy;while (!heap.isEmpty()) {ListNode node = heap.poll();current.next = node;current = current.next;if (node.next != null) {heap.offer(node.next);}}return dummy.next;}
add 6 to result
0 / 1
Solution
public ListNode mergeKLists(List<ListNode> lists) {if (lists == null || lists.isEmpty()) {return null;}List<ListNode> nonEmpty = new ArrayList<>();for (ListNode head : lists) {if (head != null) {nonEmpty.add(head);}}if (nonEmpty.isEmpty()) {return null;}PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));for (ListNode head : nonEmpty) {heap.offer(head);}ListNode dummy = new ListNode(0);ListNode current = dummy;while (!heap.isEmpty()) {ListNode node = heap.poll();current.next = node;current = current.next;if (node.next != null) {heap.offer(node.next);}}return dummy.next;}
merge k sorted arrays
0 / 19
What is the time complexity of this solution?
O(N + Q)
O(4ⁿ)
O(2ⁿ)
O(n * log k)