Merge K Sorted Arrays

lintcode 486

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.

public class Solution {
    /**
     * @param arrays: k sorted integer arrays
     * @return: a sorted array
     */
    class Point{
        int indexX;
        int indexY;
        int value;
        public Point(int indexX, int indexY, int value) {
            this.indexX = indexX;
            this.indexY = indexY;
            this.value = value;
        }
    }
    public int[] mergekSortedArrays(int[][] arrays) {
        List<Integer> list = new ArrayList<>();
        PriorityQueue<Point> queue = new PriorityQueue<>(arrays.length, new Comparator<Point>(){
            public int compare (Point a, Point b) {
                return a.value - b.value;
            }
        });
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0)
                queue.offer(new Point(i, 0, arrays[i][0]));
        }

        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            list.add(cur.value);
            if (cur.indexY < arrays[cur.indexX].length - 1) {
                queue.offer(new Point(cur.indexX, cur.indexY + 1, arrays[cur.indexX][cur.indexY + 1]));
            }
        }

        return list.stream().mapToInt(i -> i).toArray();
    }
}

Merge sort

    public int[] mergekSortedArrays(int[][] arrays) {
        if (arrays.length == 1) {
            return arrays[0];
        }
        if (arrays.length == 2) {
            return merge(arrays[0], arrays[1]);
        }

        int[] left = mergekSortedArrays(Arrays.copyOfRange(arrays, 0, arrays.length / 2));
        int[] right = mergekSortedArrays(Arrays.copyOfRange(arrays, arrays.length / 2, arrays.length));
        return merge(left, right);
    }

    public int[] merge(int[] first, int[] second) {
        List<Integer> res = new ArrayList<>();
        int firstStart = 0;
        int secondStart = 0;
        while (firstStart < first.length && secondStart < second.length) {
            if (first[firstStart] > second[secondStart]) {
                res.add(second[secondStart]);
                secondStart++;
            } else {
                res.add(first[firstStart]);
                firstStart++;
            }
        }
        while(firstStart < first.length) {
            res.add(first[firstStart]);
            firstStart++;
        }
        while(secondStart < second.length) {
            res.add(second[secondStart]);
            secondStart++;
        }
        return res.stream().mapToInt(i -> i).toArray();
    }