# Merge k Sorted Arrays

Posted on

Problem

Please review my answer for this interview question:
Merge k sorted arrays, using min heap.

``````import java.util.*;
public class MinHeap{
public static class HeapItem implements Comparable<HeapItem>{
int[] array;
int index;        // the index of current element
public HeapItem(int[] arr, int index) {
array = arr;
index = 0;
}
@Override
public int compareTo(HeapItem h){
if(array[index] > h.array[h.index]){
return 1;
}else if(array[index] < h.array[h.index]){
return -1;
}else{
return 0;
}
}
}
public static List<Integer> mergeArrays(int[][] arrays) {
if (arrays == null || arrays.length == 0) {
throw new IllegalArgumentException("Invalid input!");
}
// priority queue is heap in Java
PriorityQueue<HeapItem> pq = new PriorityQueue<HeapItem>();
// add arrays to the heap
for (int i = 0; i < arrays.length; i++) {
}
List<Integer> result = new ArrayList<Integer> ();
while (!pq.isEmpty()) {
HeapItem current = pq.remove();
if (current.index < current.array.length-1) {
}
}
return result;
}
public static void main(String[] args){
int[] arr1 = {1, 3, 5, 7};
int[] arr2 = {2, 4, 6, 8};
int[] arr3 = {0, 9, 10, 11};
System.out.println(mergeArrays(new int[][] {arr1, arr2, arr3}));
}
}
``````

Solution

# Bug

This might be a typo, but when I ran your program it infinitely looped. The problem was in your constructor:

``````  public HeapItem(int[] arr, int index) {
array = arr;
index = 0;
}
``````

Here, you are setting `index` to 0 when you should be setting it to the input argument, like this:

``````  public HeapItem(int[] arr, int index) {
array = arr;
this.index = index;
}
``````

# Reuse HeapItem

Your code all seemed very reasonable to me. There is just one small improvement I would make here:

``````      if (current.index < current.array.length-1) {
}
``````

I would just reuse `current` instead of creating a new `HeapItem`, like this:

``````      if (current.index < current.array.length-1) {
current.index++;
}
``````

# Create result list with exact size

One other small thing you could do is compute the output list size, when you are iterating through the arrays. That way, you could create `result` with the correct size instead of having it autoexpand as you add elements to it.

``````  int outputSize = 0;
for (int i = 0; i < arrays.length; i++) {