Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Merge K Sorted Arrays

Merge K Sorted Arrays

Master this topic with zero to advance depth.

Merge K Sorted Arrays

Merging multiple sorted arrays can be done efficiently using a Min-Heap. By keeping the current element of each array in the heap, we can always extract the smallest element in O(log K) time. Alternatively, Divide and Conquer can merge them in pairs.

You are given k sorted arrays. Merge all the arrays into one sorted array and return it.

Visual Representation

Arrays: [1, 4, 5] [1, 3, 4] [2, 6] Heap state (Min-Heap of elements from each array): [1, 1, 2] -> Pop 1 [4, 1, 2] -> Pop 1 [4, 3, 2] -> Pop 2 ... Result: [1, 1, 2, 3, 4, 4, 5, 6]
Hard

Examples

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Merging the three lists: [1,4,5], [1,3,4], [2,6] results in [1,1,2,3,4,4,5,6].

Input: lists = []
Output: []

Empty list.

Approach 1

Level I: Brute Force (Flatten and Sort)

Intuition

Collect all elements from all K arrays into a single list, sort that list, and return it. This is simple but doesn't take advantage of the fact that each individual array is already sorted.

⏱ O(N log N) where N is the total number of elements.💾 O(N) to store all elements in a new list.

Detailed Dry Run

All ElementsSorted Result
[1,4,5, 1,3,4, 2,6][1,1,2,3,4,4,5,6]
java
import java.util.*;

public class Main {
    public static int[] mergeKSortedArrays(int[][] arrays) {
        List<Integer> list = new ArrayList<>();
        for (int[] arr : arrays) {
            for (int val : arr) list.add(val);
        }
        Collections.sort(list);
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) result[i] = list.get(i);
        return result;
    }
    public static void main(String[] args) {
        int[][] arrays = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        System.out.println(Arrays.toString(mergeKSortedArrays(arrays)));
    }
}
Approach 2

Level II: Better Solution (Divide and Conquer)

Intuition

Merge the K arrays in pairs. In the first pass, merge array 1 with 2, 3 with 4, etc. Repeat this process until only one sorted array remains. This reduces the number of arrays logarithmically (log K).

⏱ O(N log K) where N is total elements and K is number of arrays.💾 O(N) for the result array.

Detailed Dry Run

StepPairs MergedResult Arrays
1[1,4,5] + [1,3,4][1,1,3,4,4,5]
1[2,6][2,6]
2[1,1,3,4,4,5] + [2,6][1,1,2,3,4,4,5,6]
java
import java.util.*;

public class Main {
    public static int[] mergeKSortedArrays(int[][] arrays) {
        if (arrays.length == 0) return new int[0];
        return mergeSort(arrays, 0, arrays.length - 1);
    }
    private static int[] mergeSort(int[][] arrays, int left, int right) {
        if (left == right) return arrays[left];
        int mid = left + (right - left) / 2;
        int[] l = mergeSort(arrays, left, mid);
        int[] r = mergeSort(arrays, mid + 1, right);
        return mergeTwo(l, r);
    }
    private static int[] mergeTwo(int[] a, int[] b) {
        int[] res = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) {
            res[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
        }
        while (i < a.length) res[k++] = a[i++];
        while (j < b.length) res[k++] = b[j++];
        return res;
    }
    public static void main(String[] args) {
        int[][] arrays = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        System.out.println(Arrays.toString(mergeKSortedArrays(arrays)));
    }
}
Approach 3

Level III: Optimal Solution (Min Heap)

Intuition

Use a Min-Heap to store the first element of each array along with its source array index and element index. Repeatedly extract the minimum element and insert the next element from the same array into the heap.

⏱ O(N log K) where N is total elements and K is number of arrays.💾 O(K) for the Min-Heap.

Detailed Dry Run

Min-Heap Merge Process

arrays = [[1, 4], [1, 3], [2, 6]]

Heap (val, array_idx, element_idx): 1. Push roots: [(1,0,0), (1,1,0), (2,2,0)] 2. Pop (1,0,0) -> Res: [1]. Push (4,0,1). Heap: [(1,1,0), (2,2,0), (4,0,1)] 3. Pop (1,1,0) -> Res: [1, 1]. Push (3,1,1). Heap: [(2,2,0), (3,1,1), (4,0,1)]
java
import java.util.*;

public class Main {
    static class Element {
        int val, arrayIdx, elemIdx;
        Element(int v, int a, int e) { val = v; arrayIdx = a; elemIdx = e; }
    }
    public static int[] mergeKSortedArrays(int[][] arrays) {
        PriorityQueue<Element> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        int totalSize = 0;
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0) {
                minHeap.offer(new Element(arrays[i][0], i, 0));
                totalSize += arrays[i].length;
            }
        }
        int[] result = new int[totalSize];
        int k = 0;
        while (!minHeap.isEmpty()) {
            Element curr = minHeap.poll();
            result[k++] = curr.val;
            if (curr.elemIdx + 1 < arrays[curr.arrayIdx].length) {
                minHeap.offer(new Element(arrays[curr.arrayIdx][curr.elemIdx + 1], curr.arrayIdx, curr.elemIdx + 1));
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] arrays = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        System.out.println(Arrays.toString(mergeKSortedArrays(arrays)));
    }
}
← Previous QuestionMaximum Sum of Two Non-Overlapping Subarrays
Next Question →First Missing Positive