Merge k Sorted Lists

Leetcode Daily Challenge (12th March, 2023)

12 March, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

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.

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

Problem Explanation with examples:-

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: []
Explanation: The input list is empty, so the answer is also empty.

Example 3

Input: lists = [[]]
Output: []
Explanation: The input contains one empty list, so the answer is also empty.

Example 4

Input: lists = [[6,7,8,9,10],[1,2,3,4,5]]
Output: [1,2,3,4,5,6,7,8,9,10]
Explanation: The linked-lists are: 1->2->3->4->5, 6->7->8->9->10. After merging them, we get 1->2->3->4->5->6->7->8->9->10.

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.

Intuition:-

The non-complex way would be to put all the values separately with their frequencies out of all the lists and then create a new linked list in sorted order.
For storing the values and their frequencies, a dictionary or another list can be used along with their frequencies.

Solution:-

Create a dictionary to store the values and their frequencies.
Traverse through all the lists and store the values and their frequencies in the dictionary.
Sort the dictionary in ascending order based on the keys.
Create a new linked list head and initialize a temp variable to it.
Traverse through the dictionary and run a while loop which will run for the number of times the value is present in the dictionary.
Create a new node with the value and append it to the linked list.
Finally set the next of the last node to None.
Return the head.next of the linked list as the 1st node is a dummy node.

Code:-

JAVA Solution

import java.util.*;

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Map<Integer, Integer> mp = new HashMap<>();
        for (ListNode i : lists) {
            ListNode temp = i;
            while (temp != null) {
                if (!mp.containsKey(temp.val)) {
                    mp.put(temp.val, 1);
                } else {
                    mp.put(temp.val, mp.get(temp.val) + 1);
                }
                temp = temp.next;
            }
        }
        
        Map<Integer, Integer> mps = new TreeMap<>(mp);
        ListNode head = new ListNode(0);
        ListNode temp = head;
        for (Map.Entry<Integer, Integer> entry : mps.entrySet()) {
            int i = entry.getKey();
            int z = entry.getValue();
            while (z > 0) {
                ListNode x = new ListNode(i);
                temp.next = x;
                temp = temp.next;
                z--;
            }
        }
        
        temp.next = null;
        return head.next;
    }
}

Python Solution

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        mp = {}
        for i in lists:
            temp = i
            while temp:
                if mp.get(temp.val,-1) == -1:
                    mp[temp.val] = 1
                else:
                    mp[temp.val] += 1
                temp = temp.next
        
        mps = OrderedDict(sorted(mp.items()))
        head = ListNode(0)
        temp = head
        for i in mps:
            z = mps[i]
            while z > 0:
                x = ListNode(i)
                temp.next = x
                temp = temp.next
                z -= 1
        
        temp.next = None

        return head.next

Complexity Analysis:-

TIME:-

Time complexity is O(n*m) where n is the number of lists and m is the maximum number of nodes in a list.

SPACE:-

Space complexity is O(n), as we are using a dictionary to store the values and the maximum keys we can have is n.