Given k sorted arrays of varying lengths, merge these k sorted arrays into one sorted array.

For example, given 3 arrays:

The resulting array should be like

Companies this problem is asked in## Merge k sorted arrays divide and conquer

Since all the input arrays are sorted, the first element in the output sorted array will be one of these first elements of input arrays. How can we find the minimum among all the elements plucked from the first index of each array? Easy, take those k elements (there are k arrays, so k first elements) and build a min-heap. The root of the min-heap will be the least element among each of the first elements of the given k sorted arrays, i.e.

result[0] = min(arr1[0], arr2[0], arr3[0]…arrK[0])

The initial root above will be the first element in the *result array*. Now the second element for the *result array* can be found from the set of first elements of all input arrays except the array from which the first element of result array was taken. For example, if arr1 had the least of all first elements while finding the initial root, then:

result[1] = min(arr1[1], arr2[0], arr3[0] … arrK[0])

Next iteration, 5 will be picked and put into the result array and index of arr 3 will be increased.

After putting 5 in the result array, we will move the next element in array 3 to the min-heap.

In order to know which array gave the minimum element at a particular time, we will store additional information of about array and index at which minimum element was.

If `i` represents the array number, and `j` represents the index of the minimum number currently in the heap from the `i ^{th}` array, then we add

`(j+1)`element to the min-heap next and re-heapify.

^{th}If we have put all the element from the

`i`array in the heap then we need to reduce the size of min-heap to

^{th}`k-1`.

Follow the procedure for `(n-1)*k` times. When all array elements are processed the result array will be the sorted array for all `nk` element.

## Algorithm

- Build min heap with the first element of all k arrays.
- Pick the root of min element and put it in the result array.
- If there are remaining elements in the array, put next element at the root of min heap and heapify again
- If all elements are already of an array are processed, reduce the size of min heap by 1.
- Repeat step 2, 3 and 4 till min heap is empty.

### Show me the implementation

package com.company; import java.util.PriorityQueue; /** * Created by sangar on 2.12.18. */ public class MergeKSortedArrays { private class HeapNode { public int arrayNum; public int index; public int value; public HeapNode(int arrayNum, int index, int value) { this.arrayNum = arrayNum; this.index = index; this.value = value; } } public int[] mergeKSortedArrays(int[][] arrays) { if (arrays == null) return null; PriorityQueue<HeapNode> minHeap = new PriorityQueue<>(arrays.length, (HeapNode a, HeapNode b) -> a.value - b.value); int size = 0; for (int i = 0; i < arrays.length; i++) { size += arrays[i].length; } int[] result = new int[size]; // k * n //add first elements in the array to this heap for (int i = 0; i < arrays.length; i++) { minHeap.add(new HeapNode(i, 0, arrays[i][0])); } //Complexity O(n * k * log k) for (int i = 0; i < size; i++) { //Take the minimum value and put into result HeapNode node = minHeap.poll(); if (node != null) { result[i] = node.value; if (node.index + 1 < arrays[node.arrayNum].length) { //Complexity of O(log k) minHeap.add(new HeapNode(node.arrayNum, node.index + 1, arrays[node.arrayNum][node.index + 1])); } } } return result; } }

The complexity of the code to **merge k sorted arrays** is `O(nklogk)` along with space complexity of `O(k)`.

Please share if there is something wrong or missing. If you are preparing for an interview, please sign up to receive interview preparation kit for free.