About usWhy usInstructorsReviewsCostFAQContactBlogGet Started

Merge K Sorted Arrays

This is a popular Facebook problem. 

Given K sorted arrays arr, of size N each, merge them into a new array res, such that res is a sorted array.

 Assume N is very large compared to K. N may not even be known. The arrays could be just sorted streams, for instance, timestamp streams.

All arrays might be sorted in increasing manner or decreasing manner. Sort all of them in the manner they appear in input.

- Repeats are allowed.

- Negative numbers and zeros are allowed.

- Assume all arrays are sorted in the same order. Preserve that sort order in output.

- It is possible to find out the sort order from at least one of the arrays.


Example

Input:

K = 3, N =  4

arr = [[1, 3, 5, 7],

          [2, 4, 6, 8],

          [0, 9, 10, 11]]


Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

A solution which dumps all elements from all arrays into one massive heap, and then extracts the elements one by one into a sorted output may pass, but is not acceptable. These issues should go away when we have a more nuanced backend.


Notes

Input Format: There is only one argument: 2D Integer array arr.

Here, arr[i][j] denotes value at index j of ith input array, 0-based indexing. So, arr is K * N size array.

Output: Return an integer array res, containing all elements from all individual input arrays combined.


Solutions:

First step is to check if the input is in increasing sorted manner or in decreasing sorted manner. Let's solve it for increasingly sorted input.

A naive approach would be to add all elements to one collection and then sort them out. We can build on our solution following the idea of the naive solution. At any given point of time, the smallest element would be from the pool of candidate smallest elements formed by adding the elements at start of all arrays. When we remove the smallest element from the pool, we will add the next element from that array.

We can maintain a min priority queue to carry out these operations. For decreasingly sorted manner, maintain a max priority queue.


Time Complexity: 

O(NK*Log(K))

Space Complexity: 

O(K + NK)