Iteration

K-Merge

Given k sorted arrays arrs, merge them together and return the new array.

Example:

First Few Test Cases:

The idea is to add all the elements to a larger array in increasing order:

To find the smallest element, we just have to consider the leftmost elements in all the arrays, because they're all sorted. We can take the min of all the leftmost numbers to get the smallest number.

We can keep taking the min over the leftmost numbers to get the next number in the array.

Many of the same numbers show up whenever we take the min. This means we should use a Heap data structure to optimize, so that taking the min is fast.

The algorithm is to put all the leftmost values into a Heap. You then pop the heap to get the min of all the values. You also have to replace the value that you removed from the Heap. By iterating this, you end up with a big sorted array.

Here's the code for this:

Time Complexity O(nlogk)O(n \log k). We pop the heap whenever we add a new element to the array. There are kk elements in the Heap, and the heap is a balanced tree, so this takes O(logk)O(\log k) time. We do this for all the nn elements. This gives nO(logk)=O(nlogk)n*O(\log k) = O(n \log k) time.

Space Complexity O(n)O(n). The Heap requires O(k)O(k) space, and the solution array requires O(n)O(n). This is just O(k)+O(n)=O(k+n)=O(n)O(k)+O(n) = O(k+n) = O(n) since n is always larger than k.

Mark as Completed:
Submits:
mergeSortedArrays
Test your code to get an output here!
mergeSortedArrays(
)
Test your code to get an output here!