Merge k Sorted Arrays

Given k sorted integer arrays, merge them into one sorted array.

Example:

Given 3 sorted arrays:

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

return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].

Solution:

1. Convert data from int array to List<List<Integer>>, merge two List<Integer> at a time until there is only one left. O(nlogk) Space: O(n) with O(nk) garbages
2. Use a PriorityQueue to store the data of the first column, then move the smallest element to right and add this value to result until the PriorityQueue is empty. O(nlogk) Space: O(k). Better solution!

Code: version 1:

public List<Integer> mergekSortedArrays(int[][] arrays) {
    if (arrays == null || arrays.length == 0) {
        return new ArrayList<Integer>();
    }
    List<List<Integer>> list = new ArrayList<>();

    for (int i = 0; i < arrays.length; i++) {
        ArrayList<Integer> temp = new ArrayList<>();
        for (int j = 0; j < arrays[i].length; j++) {
            temp.add(arrays[i][j]);
        }
        list.add(temp);
    }

    while (list.size() > 1) {
        List<List<Integer>> tempList = new ArrayList<>();
        for (int i = 0; i + 1 < list.size(); i += 2) {
            tempList.add(merge(list.get(i), list.get(i + 1)));
        }
        if (list.size() % 2 == 1) {
            tempList.add(list.get(list.size() - 1));
        }
        list = tempList;
    }
    return list.get(0);
}
private List<Integer> merge(List<Integer> a, List<Integer> b) {
    List<Integer> c = new ArrayList<>();
    int i = 0;
    int j = 0;
    while (i < a.size() && j < b.size()) {
        if (a.get(i) <= b.get(j)) {
            c.add(a.get(i++));
        } else {
            c.add(b.get(j++));
        }
    }
    while (i < a.size()) {
        c.add(a.get(i++));
    }
    while (j < b.size()) {
        c.add(b.get(j++));
    }
    return c;
}

version 2:

class Element {
    int row;
    int col;
    int val;
    public Element(int inRow, int inCol, int inVal) {
        this.row = inRow;
        this.col = inCol;
        this.val = inVal;
    }
}
public class Solution {
    public List<Integer> mergekSortedArrays(int[][] arrays) {
        if (arrays == null || arrays.length == 0 || arrays[0].length == 0) {
            return new ArrayList<>();
        }
        Queue<Element> queue = new PriorityQueue<>(arrays.length, 
            new Comparator<Element>() {
                public int compare(Element a, Element b) {
                    return a.val - b.val;
                }
            });
        for (int i = 0; i < arrays.length; i++) {
            Element e = new Element(i, 0, arrays[i][0]);
            queue.offer(e);
        }
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            Element e = queue.poll();
            result.add(e.val);
            if (e.col + 1 < arrays[e.row].length) {
                queue.offer(new Element(e.row, e.col + 1, arrays[e.row][e.col + 1]));
            }
        }
        return result;
    }
}