# Merge K Sorted Arrays

`Array`, `Heap`, `Priority Queue`

### Description

Given _k _sorted integer arrays, merge them into one sorted array.

### Example

Example 1:

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

Example 2:

``````Input:
[
[1,2,3],
[1,2]
]
Output: [1,1,2,2,3]``````

### Challenge

Do it in O(N log k).

• _N - _is the total number of integers.

• _k - _is the number of arrays.

## Solution

#### LintCode official - Heap (Priority Queue)

``````/**
* This reference program is provided by @jiuzhang.com
*/

class Element {
public int row, col, val;
Element(int row, int col, int val) {
this.row = row;
this.col = col;
this.val = val;
}
}

public class Solution {
private Comparator<Element> ElementComparator = new Comparator<Element>() {
public int compare(Element left, Element right) {
return left.val - right.val;
}
};

/**
* @param arrays k sorted integer arrays
* @return a sorted array
*/
public int[] mergekSortedArrays(int[][] arrays) {
if (arrays == null) {
return new int[0];
}

int total_size = 0;
Queue<Element> Q = new PriorityQueue<Element>(
arrays.length, ElementComparator);

for (int i = 0; i < arrays.length; i++) {
if (arrays[i].length > 0) {
Element elem = new Element(i, 0, arrays[i][0]);
total_size += arrays[i].length;
}
}

int[] result = new int[total_size];
int index = 0;
while (!Q.isEmpty()) {
Element elem = Q.poll();
result[index++] = elem.val;
if (elem.col + 1 < arrays[elem.row].length) {
elem.col += 1;
elem.val = arrays[elem.row][elem.col];
}
}

return result;
}
}``````

#### Divide and Conquer

``````public class Solution {
/**
* @param arrays: k sorted integer arrays
* @return: a sorted array
*/
public int[] mergekSortedArrays(int[][] arrays) {
if(arrays == null || arrays.length == 0) return new int[0];
return divide_conquer(arrays);
}

private int[] divide_conquer(int[][] arrays){
while(arrays.length>1){
int n = arrays.length/2;
if(arrays.length%2 == 1) n++;

int temp[][] = new int[n][];
int idx = 0;
for(int i=0;i<arrays.length && i+1<arrays.length; i+=2){
temp[idx++] = mergeTwoSortedArray(arrays[i], arrays[i+1]);
}
if(arrays.length%2 == 1) temp[idx++] = arrays[arrays.length-1];

arrays = temp;
}
return arrays[0];
}

private int[] mergeTwoSortedArray(int[] arr1, int[] arr2){
if(arr1 == null || arr1.length == 0) return arr2;
if(arr2 == null || arr2.length == 0) return arr1;

int totalLen = arr1.length+arr2.length;
int[] res = new int[totalLen];
int idx=0;
int i=0, j=0;

while(i<arr1.length && j<arr2.length){
if(arr1[i]<=arr2[j]){
res[idx++] = arr1[i++];
}else{
res[idx++] = arr2[j++];
}
}

while(i<arr1.length){
res[idx++] = arr1[i++];
}

while(j<arr2.length){
res[idx++] = arr2[j++];
}

return res;
}
}``````

Last updated