Interview Questions – Merge K sorted lists efficiently

Problem

Given K sorted arrays write an efficient algorithm to merge them into one.

Example

Given the below sorted array where K = 3

k₁ : 4 5 6            k₂ : 1 2 3           k₃ : 8 9 10

output sorted list : 1 2 3 4 5 6 8 9 10

Constraints

[1] 1 < k < 10000

[2] List contains only contains Integer

[3] Assume sorting is in memory only.

Solution

Looking at the problem first thing is all the lists are sorted in nature. So if we take the route where L₁, L_2, … L_k then we can take the first two lists (L₁, L₂) sort them then the output of this combined list is further sorted L₃ and so on. okay nice! seems like we got the solution. But can you guess the time complexity?

lets consider total elements in k lists are n. So the maximum total comparison would be O(n^k) where each element will be compared to K times. Is this the best we can do?

Lets try to think one level deep, so what is the primary operation, it is basically finding a minimum for all the K list at each iteration. Can you think of any data structure that can extract min& insertion a key faster? I can think of a priority queue(min heap). It seems to satisfy O(log₂k) min key extraction and O(log₂k) insertion time & O(1) min peek time. Lets try to implement this and then discuss the time complexity.

Algorithm

1. Insert first element from the K list in the min Priority Queue.
2. While the Priority queue is not empty
   • Remove min element priority queue and insert in output array.
   • Insert the next element from the K^th list from where the last polled min element belongs to.

Main.java

import working.example.tech.InterviewQuestions.MergeKSortedList;
import working.example.tech.interfaces.TestCaseRunner;
public class Main {
    public static void main(String[] args) {
        TestCaseRunner mergeKlist = new MergeKSortedList();
        mergeKlist.RunTest();
    }
}

MergeKSortedList.java

package working.example.tech.InterviewQuestions;

import java.util.*;

public class MergeKSortedList implements working.example.tech.interfaces.TestCaseRunner{
    @Override
    public void RunTest() {
       Vector<List<Integer>> vec = new Vector<>();
       vec.add(new ArrayList<>());
       vec.add(new ArrayList<>());
       vec.add(new ArrayList<>());
       vec.add(new ArrayList<>());
        PriorityQueue<PriorityQueueNode> priorityQueue =
                new PriorityQueue<>(new PriorityQueueNodeComparator());
        // list 1
        vec.get(0).add(1);
        vec.get(0).add(2);
        vec.get(0).add(4);
        // list 2
        vec.get(1).add(3);
        vec.get(1).add(5);
        vec.get(1).add(10);
        // list 3
        vec.get(2).add(6);
        vec.get(2).add(8);
        vec.get(2).add(12);
        // list 4
        vec.get(3).add(7);
        vec.get(3).add(9);
        vec.get(3).add(11);
        priorityQueue.add(new PriorityQueueNode(vec.get(0).get(0), 0, 0));
        priorityQueue.add(new PriorityQueueNode(vec.get(1).get(0), 0, 1));
        priorityQueue.add(new PriorityQueueNode(vec.get(2).get(0), 0, 2));
        priorityQueue.add(new PriorityQueueNode(vec.get(3).get(0), 0, 3));
        while(!priorityQueue.isEmpty()) {
            int val = priorityQueue.peek().val;
            int listIndex = priorityQueue.peek().listIndex;
            int listId = priorityQueue.peek().listId;
            System.out.println(val);
            priorityQueue.poll();
            if ((listIndex + 1) < vec.get(listId).size()) {
                priorityQueue.add(
                        new PriorityQueueNode(vec.get(listId).get(listIndex + 1),
                                listIndex + 1, listId));
            }
        }
    }

    @Override
    public void showOut() {

    }

    public class PriorityQueueNode {
        private int val;
        private int listIndex;
        private int listId;
        PriorityQueueNode(int val, int listIndex, int listId) {
            this.val = val;
            this.listIndex = listIndex;
            this.listId = listId;
        }
    }

    public class PriorityQueueNodeComparator implements Comparator<PriorityQueueNode> {
        @Override
        public int compare(PriorityQueueNode o1, PriorityQueueNode o2) {
            int key1 = o1.val;
            int key2 = o2.val;
            if (key2 == key1) {
                return 0;
            } else if (key1 < key2) {
                return -1;
            } else {
                return 1;
            }
        }
    }

}

Complexity

Auxiliary space complexity: O(n)

Time complexity: klog₂(k) + n(2*log₂(k)) ~ O(nk(log₂k))

where n is total number of elements and K is number of list