9.8 Merge K Sorted Arrays

9.8.1 Problem Metadata

9.8.2 Description

Given k sorted integer arrays, merge them into a single sorted array that contains all elements from the inputs.

9.8.3 Examples

Input: [[1,4,7],[2,5],[3,6,9]]
Output: [1,2,3,4,5,6,7,9]

9.8.4 Constraints

  • 1 <= k <= 10^3
  • Total number of elements across all arrays n <= 10^5
  • Each array is sorted in non-decreasing order

9.8.5 Solution - Min Heap of Array Entries

9.8.5.1 Walkthrough

Store each array’s current front element inside a min heap, keyed by value. Pop the smallest element, append it to the answer, then advance the pointer for the array it came from and push the next value (if any). Because each push/pop costs log k and every element is processed once, the merge preserves overall sorted order efficiently.

9.8.5.2 Analysis

  • Time Complexity: O(n log k), where n is the total element count
  • Space Complexity: O(k) for the heap plus O(n) for the output

9.8.5.3 Implementation Steps

  1. Compute the total element count to size the output array.
  2. Push (arrayIndex, elementIndex) pairs for the first element of each non-empty array into a min heap ordered by value.
  3. Repeatedly pop the smallest entry, append the value to the output, and advance that array’s index.
  4. If the array still has elements, push the updated entry back into the heap.
  5. Return the filled output array.

9.8.5.4 Code - Java

class ArrayEntry implements Comparable<ArrayEntry> {
    int[] array;
    int index;

    ArrayEntry(int[] array, int index) {
        this.array = array;
        this.index = index;
    }

    int value() {
        return array[index];
    }

    @Override
    public int compareTo(ArrayEntry other) {
        return Integer.compare(this.value(), other.value());
    }
}

public int[] mergeKSortedArrays(int[][] arrays) {
    PriorityQueue<ArrayEntry> minHeap = new PriorityQueue<>();
    int total = 0;

    for (int[] array : arrays) {
        total += array.length;
        if (array.length > 0) {
            minHeap.offer(new ArrayEntry(array, 0));
        }
    }

    int[] merged = new int[total];
    int write = 0;

    while (!minHeap.isEmpty()) {
        ArrayEntry current = minHeap.poll();
        merged[write++] = current.value();
        current.index++;
        if (current.index < current.array.length) {
            minHeap.offer(current);
        }
    }

    return merged;
}