Merge K Sorted Arrays

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

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 Elements	Sorted 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

Step	Pairs Merged	Result 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):
Push roots: [(1,0,0), (1,1,0), (2,2,0)]
Pop (1,0,0) -> Res: [1]. Push (4,0,1). Heap: [(1,1,0), (2,2,0), (4,0,1)]
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)));
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready

Updated: Weekly

← Previous QuestionMaximum Sum of Two Non-Overlapping Subarrays

Next Question →First Missing Positive

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.