23. Merge k Sorted Lists 🔥

Hard

Problem:

Merge k sorted lists into one sorted list.

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

https://leetcode.com/problems/merge-k-sorted-lists/

What to learn:

Heap queue (or heapq) in Python

Heap data structure is mainly used to represent a priority queue. In Python, it is available using the “heapq” module.

The property of this data structure in Python is that each time the smallest heap element is popped(min-heap). Whenever elements are pushed or popped, heap structure is maintained. The heap[0] element also returns the smallest element each time.

import heapq
 
li = [5, 7, 9, 1, 3]

# Convert the list into a heap
heapq.heapify(li)

# The created heap is :  [1, 3, 9, 7, 5]
print ("The created heap is : ",(list(li)))

• heapify(iterable): This function is used to convert the iterable into a heap data structure. i.e. in heap order.

• heappush(heap, ele): This function is used to insert the element mentioned in its arguments into a heap. The order is adjusted, so that heap structure is maintained.

• heappop(heap): This function is used to remove and return the smallest element from the heap. The order is adjusted, so that heap structure is maintained.

• heappushpop(heap, ele):- This function combines the functioning of both push and pop operations in one statement, increasing efficiency. Heap order is maintained after this operation.

• heapreplace(heap, ele):- This function also inserts and pops elements in one statement, but it is different from the above function. In this, the element is first popped, then the element is pushed. i.e, the value larger than the pushed value can be returned. heapreplace() returns the smallest value originally in the heap regardless of the pushed element as opposed to heappushpop().

• nlargest(k, iterable, key = fun): This function is used to return the k largest elements from the iterable specified and satisfy the key if mentioned.

• nsmallest(k, iterable, key = fun): This function is used to return the k smallest elements from the iterable specified and satisfy the key if mentioned.

Solution:

1. Store the root of each linked list in a heap

2. After the heap extraction, the next node is stored again.

import heapq

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        root = result = ListNode(None)
        heap = []

        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i, lists[i]))

        while heap:
            node = heapq.heappop(heap)
            idx = node[1]
            result.next = node[2]
            result = result.next

            if result.next:
                heapq.heappush(heap, (result.next.val, idx, result.next))
        return root.next

Time Limit Exceeded

import heapq
import sys

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        new_lists = []

        for list in lists:
            sub_list = []
            node = list
            while node is not None:
                sub_list.append(node.val)
                node = node.next
            new_lists.append(sub_list)

        heapq.heapify(new_lists)
        result = []
        size = len(new_lists)
        total = 0
        for list in new_lists:
            for _ in list:
                total += 1

        while total > 0:
            total -= 1
            min_val = sys.maxsize
            min_list = []
            for idx, list in enumerate(new_lists):
                if len(list) > 0:
                    if list[0] < min_val:
                        min_val = list[0]
                        min_list = list
                if idx == size - 1:
                    result.append(min_val)
                    heapq.heappop(min_list)
                
        # Convert a List to ListNode
        head = ListNode(-1)
        node = head
        for value in result:
            node.next = ListNode(value)
            node = node.next
        return head.next