Topics › Heaps › Medium Problems

Merge K Sorted Arrays

Medium TUF ID 713 SDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given k arrays, each sorted in non-decreasing order. The arrays may have different lengths, and some may be empty. Return one sorted array containing every element of every input array.

The Blind 75 list files this row under Merge k Sorted Lists (LeetCode 23): the inputs are k sorted linked lists and the output is one sorted linked list. The algorithm is identical; the last section gives the linked-list code.

Let N be the total number of elements. Constraints: 0 ≤ k ≤ 10^4, N ≤ 10^5, values fit in an int.

Example 1

arrays = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
answer = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Example 2

arrays = [[1, 4, 5], [1, 3, 4], [2, 6]]
answer = [1, 1, 2, 3, 4, 4, 5, 6]     // duplicates across arrays are all kept

Approach 1: Brute force, concatenate and sort

Intuition. Forget that the inputs are sorted: pour every element into one array and sort it. It is correct and short, and it is the baseline any smarter method must beat. Its weakness is that the sort redoes work the inputs had already done.

Algorithm.

1. Count the total N and allocate the output.
2. Copy every element of every array into it.
3. Sort the output.

static int[] bruteForce(int[][] arrays) {
    int total = 0;
    for (int[] a : arrays) total += a.length;
    int[] out = new int[total];
    int t = 0;
    for (int[] a : arrays) {
        for (int v : a) out[t++] = v;
    }
    Arrays.sort(out);
    return out;
}

Complexity. Time O(N log N) for the sort. Space O(N) for the output (plus the sort’s internal stack).

Approach 2: Better, divide and conquer

Intuition. Merging two sorted arrays is a linear-time two-pointer walk. The natural next idea is to merge the arrays one after another into a growing result, but that is slow: the result is re-copied on every merge, so the first array’s elements are copied k - 1 times and the total cost is O(N · k).

Merge sort’s trick fixes this. Merge the arrays in pairs, then merge the pairs in pairs, and so on, like a tournament bracket. There are only log2 k rounds, and in each round every element is copied exactly once, so the total is O(N log k).

Algorithm.

1. If there are no arrays, return an empty array.
2. mergeRange(lo, hi): if lo == hi, return a copy of that array; otherwise merge the results of mergeRange(lo, mid) and mergeRange(mid + 1, hi).

static int[] mergeTwo(int[] a, int[] b) {
    int[] out = new int[a.length + b.length];
    int i = 0, j = 0, t = 0;
    while (i < a.length && j < b.length) out[t++] = a[i] <= b[j] ? a[i++] : b[j++];
    while (i < a.length) out[t++] = a[i++];
    while (j < b.length) out[t++] = b[j++];
    return out;
}

static int[] better(int[][] arrays) {
    if (arrays.length == 0) return new int[0];
    return mergeRange(arrays, 0, arrays.length - 1);
}

static int[] mergeRange(int[][] arrays, int lo, int hi) {
    if (lo == hi) return arrays[lo].clone();
    int mid = (lo + hi) >>> 1;
    return mergeTwo(mergeRange(arrays, lo, mid), mergeRange(arrays, mid + 1, hi));
}

Complexity. Time O(N log k): log k levels of recursion, each level touching every element once. Space O(N) for the intermediate merged arrays, plus O(log k) recursion depth.

Approach 3: Optimal, min-heap of the current fronts

Intuition. Think of each array as a queue whose front is its smallest remaining element. The next element of the output must be the smallest of the k fronts. A min-heap holding one entry per non-empty array gives that smallest front in O(log k). After taking it, the only front that changed is the one in the array we just took from, so we push that array’s next element and repeat.

Each heap entry stores the value plus enough information to find the successor: {value, arrayIndex, elementIndex}.

Algorithm.

1. Push {arrays[r][0], r, 0} for every non-empty array r.
2. While the heap is not empty: pop the smallest entry, append its value to the output, and if array r has an element at elementIndex + 1, push it.
3. Return the output.

static int[] optimal(int[][] arrays) {
    int total = 0;
    // heap entries are {value, arrayIndex, elementIndex}
    PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
    for (int r = 0; r < arrays.length; r++) {
        total += arrays[r].length;
        if (arrays[r].length > 0) pq.offer(new int[]{arrays[r][0], r, 0});
    }
    int[] out = new int[total];
    int t = 0;
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        out[t++] = top[0];
        int r = top[1], next = top[2] + 1;
        if (next < arrays[r].length) pq.offer(new int[]{arrays[r][next], r, next});
    }
    return out;
}

Dry run on Example 2. Entries are written as value(array):

When two fronts are equal, PriorityQueue may pop either one first. The output is the same either way, because equal values are interchangeable.

Complexity. Time O(N log k): every element is pushed and popped exactly once, and the heap never holds more than k entries. Space O(k) for the heap, beyond the O(N) output.

Approaches 2 and 3 have the same time bound. The heap version is usually preferred: it needs only O(k) extra memory, it works when the inputs are streams that can only be read front to back, and it produces output incrementally.

The linked-list version (Blind 75, LeetCode 23)

With linked lists, the heap can hold the nodes themselves: a node already knows its successor through next, so no indices are needed. A dummy head node avoids a special case for the first output element, and the existing nodes are relinked rather than copied.

static class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

static ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
    for (ListNode head : lists) {
        if (head != null) pq.offer(head);
    }
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        tail.next = node;
        tail = node;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}

Time O(N log k), extra space O(k) for the heap. The tests run all four methods on the same inputs, including 200 seeded random cases checked against a plain sort.

Edge cases and pitfalls

• k = 0. No arrays at all: return an empty array (or null for the list version). Approach 2 must check this before recursing on an empty range.
• Empty inner arrays or null lists. Never push them into the heap; arrays[r][0] would throw. The tests include [[], [-1], []] and [[], []].
• k = 1. The answer is a copy of the single array. Approach 2 clones it so the caller’s input is never aliased by the result.
• Comparator overflow. Write Integer.compare(x[0], y[0]), not x[0] - y[0]. The subtraction overflows for values of opposite sign near the int limits and silently breaks the heap order.
• Duplicates and negatives. Nothing special is needed; all three methods keep every copy.
• Sequential merging. Merging array 1 into array 0, then array 2 into that result, and so on looks like divide and conquer but costs O(N · k). The pairing structure is what brings it down to O(N log k).

Related problems

• Merge K sorted Lists is the linked-list version in the A2Z sheet.
• Merge two Sorted Lists is the two-way merge used as the building block.
• Merge Sorting is where the divide-and-conquer merging pattern comes from.
• Sort K sorted array uses a small heap in the same “only a few candidates can be next” way.
• Implement Min Heap shows how the heap behind PriorityQueue works.