Leetcode problem 23. Merge k Sorted Lists (HARD)

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

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: []

Similar to merging 2 sorted linked-lists, in which we need traverse through two list simultaneously using two cursors, systematically pick the smaller item from the two cursor, and move the cursors accordingly. However, we cannot do the same for k lists be cause comparing all k current cursors will take O(k) time at every steps, and that is bad.

Trying to merge a single list at a time for a total of k time is also bad, as the majority of comparison will be duplicated over and over again as you finish merging one list and move to another, resulting in an O(KN) complexity, where N is the total number of item in all list.

We can reduce the time complexity by using Priority Queue (aka min-heap).

Initially, add all lists to the queue, sorting by the top item will take O(KlogK) time.

Subsequently, keep popping the smallest item from the heap, add the top item to the merger list, and put the list back into the heap if the list is not empty (null) yet. The putting back take logK time, and is repeated once for every item of any list, which make the total run time O(NlogK) if we consider N the total number of items from all lists. This is a significant improvement.

Despite being a “hard” Leetcode problem, this is actually a very pragmatic problem to be solved and can be applied in a lot of real life application comparing to other brain teasing type of “hard” problem.

This is the sample code in Kotlin.

fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.size == 0) return null
        if (lists.size == 1) return lists[0]

        //Initiate our Priority Queue with a custom Type and Comperator
        val pList = PriorityQueue(lists.size) { o1: ListNode, o2: ListNode ->
            return@PriorityQueue when {
                o1.`val` > o2.`val` -> 1
                o1.`val` == o2.`val` -> 0
                else -> -1
            }
        }
        
        //Add all lists to the queue
        lists.forEach { if (it != null) pList.add(it) }
        var newList: ListNode? = null
        var cursor: ListNode? = null

        //Pop the top list to get the smallest item to add to the merger until 
        //all lists are emptied.
        while (pList.isNotEmpty()) {
            var top = pList.remove()
            if (newList == null) {
                newList = top
                cursor = newList
            } else {
                cursor?.next = top
                cursor = top
            }
            //Remove top item from top list, then put top list back into the queue
            //if it is not empty yet.
            top = top?.next
            if (top != null) {
                pList.add(top)
            }
        }
        return newList
    }