Merge K sorted arrays

Problem

Given K sorted arrays, write an algorithm that merges these arrays and returns a single sorted array.

Example:

Input:

[[1, 3, 4], [5, 6, 11], [2, 9, 10]]

Output:

[1, 2, 3, 4, 5, 6, 9, 10, 11]

Approach

There are multiple solutions to this problem. A possible brute force approach would be to create an array of size n*k, copy all the elements from the input arrays to it and then sort the entire array. Time complexity of this approach would be O(nk log nk) where nk is the size of the merged array.

Solution

One efficient solution is to use a min Heap (PriorityQueue in Java) of size K. At any given time the heap contains the minimum element non visited of each array. We repeatedly extract the minimum element from the heap and add it to the final result. We then add to the heap the next element of the array that contains the element that we just visited.

Adding an element to the heap takes O(logK) while extracting the min element takes O(1). We need to visit all elements (n*k elements in total) so the runtime complexity of this algorithm is O(nk logk) in the worst case.

int[] mergeKSortedArrays(int[][] arrays) {
    PriorityQueue<HeapNode> queue = new PriorityQueue<>();
    int resultLen = 0;

    // Add first element of each array to the queue
    for (int[] arr : arrays) {
        queue.add(new HeapNode(arr, 0));
        resultLen += arr.length;
    }

    int[] result = new int[resultLen];
    int i = 0;

    while(!queue.isEmpty()) {
        // Extract min element from the queue
        HeapNode node = queue.poll();
        result[i] = node.arr[node.index];
        i++;

        // Add to queue next element from the array that contains the current visited node
        if(node.hasNext()) {
            queue.add(new HeapNode(node.arr, node.index+1));
        }
    }

    return result;
}


// Node class implementation
class HeapNode implements Comparable<HeapNode> {
    int[] arr;
    int index;

    public HeapNode(int[] arr, int index) {
        this.arr = arr;
        this.index = index;
    }

    public boolean hasNext() {
        return this.index < this.arr.length-1;
    }

    @Override
    public int compareTo(HeapNode o) {
        return arr[index] - o.arr[o.index];
    }
}