Merge K Sorted Arrays

Question (LC.486)

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

Example

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

Maintain a minHelp of size 3

Code

private class HeapNode {
    int value;
    int row;
    int col;

    public HeapNode(int value, int row, int col) {
        this.value = value;
        this.row = row;
        this.col = col;
    }
}

// Java 8 Using Lambda
// Comparator<HeapNode> heapComp = 
//    (HeapNode n1, HeapNode n2) -> n1.value - n2.value;

private Comparator<HeapNode> HeapComp = new Comparator<HeapNode>() {
    public int compare(HeapNode n1, HeapNode n2) {
        return n1.value - n2.value;
    }
};

public List<Integer> mergekSortedArrays(int[][] arrays) {
    List<Integer> result = new ArrayList<>();

    if (arrays == null) {
        return result;
    }

    int k = arrays.length;

    Queue<HeapNode> minHeap = new PriorityQueue<>(k, HeapComp);

    // add the first col to the minHeap
    for (int i = 0; i < k; i++) {
        if (arrays[i].length < 1) {
            continue;
        }
        HeapNode newNode = new HeapNode(arrays[i][0], i, 0);
        minHeap.offer(newNode);
    }

    // update the minHeap as we go
    while (!minHeap.isEmpty()) {
        HeapNode current = minHeap.poll();
        result.add(current.value);
        // add the next element in this list
        if (current.col + 1 < arrays[current.row].length) {
            HeapNode newNode = new HeapNode(arrays[current.row][current.col+1], 
                                            current.row, current.col+1);
            minHeap.offer(newNode);
        }
    }

    return result;
}

Last updated