What is the brute force approach and complexity for Merge K Sorted Arrays?

Copy every element into one list, then sort the whole list with time complexity O(N log N) and space complexity O(N).

What is the optimal approach and complexity for Merge K Sorted Arrays?

Keep the first unused element of each array in a min-heap; pop the smallest, then push its successor with optimal time complexity O(N log K) and space complexity O(K).

How do you identify the pattern for Merge K Sorted Arrays?

Look for key signals in the prompt: "K sorted arrays" indicates Each array is sorted, so only its first unused element can be the next output from it. That is why K candidates are enough.; "merge into one sorted array" indicates At every step, take the smallest of the candidates → a min-heap of the front values.; "every element appears once" indicates Each element is pushed and popped once, so the cost is N pushes and pops, not one per array..

Merge K Sorted Arrays

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelK-way Merge — Merge K sorted (heap with one front per list)

Complexity:O(N log N)→O(N log K)

Key Insight

Keep one candidate per array in a min-heap: its first unused element. Pop the smallest candidate and output it. Then push the next element from the same array. The heap never holds more than K items, because each array contributes only one candidate at a time.

Core Validity Invariant

The smallest unused element overall is always the smallest of the first unused elements of the arrays, so the heap top is always the correct next output.

Problem

You get K arrays. Each array is already sorted from smallest to largest. The arrays can have different lengths, and one of them can be empty.

Merge them into one array that holds every element, in sorted order.

Input

arr: a list of K sorted arrays. K: how many arrays there are.

Output

One sorted array that holds every element of every input array.

Example 1

Input: arr = [[2, 6, 9], [1, 5, 8], [0, 3, 4, 7]], K = 3

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

The smallest front value is 0 (from the third array), then 1, then 2, and so on. All 10 elements end up in order.

Example 2

Input: arr = [[1, 3], [], [2]], K = 3

Output: [1, 2, 3]

The empty array has nothing to add, so it is skipped.

Constraints

• Each input array is sorted from smallest to largest.
• The arrays can have different lengths, and an array can be empty.
• The values are integers.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Each array is already sorted. Which element can be the very next one I output?
2.
If I only look at the first unused element of each array, how many candidates do I have at any moment?
3.
After I take an element out of an array, which element of that same array becomes a candidate?
4.
Which data structure gives me the smallest of my candidates quickly, and how big does it need to be?
5.
If I put all N elements into that structure at the start, does it still do the job?

Brute force approach

Idea

Ignore that the arrays are already sorted. Copy all elements into one big array, then sort that array with a standard sort. Let N be the total number of elements: the sort costs O(N log N).

Thinking process

1
The answer must hold every element once. Here that is 3 + 3 + 4 = 10 values.
2
Copy them in array order: [2, 6, 9, 1, 5, 8, 0, 3, 4, 7]. This is not sorted yet, because each array is only sorted on its own.
3
A standard sort puts the 10 values in order. It is correct.
4
But it does not use the fact that each array is already sorted. It re-compares work the arrays have already done.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> mergeKArrays(vector<vector<int>>& arr, int K) {
        // Copy every element into one big list, then sort the whole thing.
        vector<int> all;
        for (int i = 0; i < K; i++) {
            all.insert(all.end(), arr[i].begin(), arr[i].end());
        }
        sort(all.begin(), all.end());
        return all;
    }
};

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public ArrayList<Integer> mergeKArrays(int[][] arr, int K) {
        // Copy every element into one big list, then sort the whole thing.
        ArrayList<Integer> all = new ArrayList<>();
        for (int i = 0; i < K; i++) {
            for (int val : arr[i]) {
                all.add(val);
            }
        }
        Collections.sort(all);
        return all;
    }
}

from typing import List

class Solution:
    def mergeKArrays(self, arr: List[List[int]], K: int) -> List[int]:
        # Copy every element into one big list, then sort the whole thing.
        all_elements: List[int] = []
        for i in range(K):
            all_elements.extend(arr[i])
        all_elements.sort()
        return all_elements

export function mergeKArrays(arr: number[][], K: number): number[] {
    // Copy every element into one big list, then sort the whole thing.
    const all: number[] = [];
    for (let i = 0; i < K; i++) {
        all.push(...arr[i]);
    }
    all.sort((a, b) => a - b);
    return all;
}

Complexity

Time O(N log N)Space O(N)

N is the total number of elements. If every array has n elements, then N = n·K, so this is O(nK log(nK)). The output array itself is O(N) space.

Better approach

Why brute force is slow

The brute force sorts all N elements from scratch, although the arrays are already in order.

What repeated work are we doing?

Each merge rewrites the whole result, so an element that sits in the result gets copied again for every later array. With K arrays it can be copied up to K times.

What information can we reuse?

Merging two sorted lists takes one linear pass. The merged result is itself sorted, so it can be merged again with the next array.

New approach

Idea

Start with an empty result. For each array in turn, merge it into the result with the two-pointer merge: at each step take the smaller of the two front values. The result is always sorted, so no sort is needed.

Thinking process

1
Merging two sorted lists needs one pass: compare the two front values, take the smaller, and move that pointer forward.
2
Merge [2, 6, 9] with [1, 5, 8] → [1, 2, 5, 6, 8, 9]. Six values, one pass.
3
Merge that result with [0, 3, 4, 7] → [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]. Done.
4
Each merge copies the whole result again. With K arrays, the early elements get copied up to K times.

Code & Implementation

better.cpp

class Solution {
public:
    vector<int> mergeKArrays(vector<vector<int>>& arr, int K) {
        // Holds everything merged so far. Starts empty.
        vector<int> result;
        for (int i = 0; i < K; i++) {
            // Merge the result with the next array, the same way merge sort merges two halves.
            vector<int> merged;
            merged.reserve(result.size() + arr[i].size());
            size_t a = 0, b = 0;
            while (a < result.size() && b < arr[i].size()) {
                if (result[a] <= arr[i][b]) merged.push_back(result[a++]);
                else merged.push_back(arr[i][b++]);
            }
            while (a < result.size()) merged.push_back(result[a++]);
            while (b < arr[i].size()) merged.push_back(arr[i][b++]);
            result.swap(merged);   // the merged list is the new result
        }
        return result;
    }
};

import java.util.ArrayList;

class Solution {
    public ArrayList<Integer> mergeKArrays(int[][] arr, int K) {
        // Holds everything merged so far. Starts empty.
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < K; i++) {
            // Merge the result with the next array, the same way merge sort merges two halves.
            ArrayList<Integer> merged = new ArrayList<>(result.size() + arr[i].length);
            int a = 0, b = 0;
            while (a < result.size() && b < arr[i].length) {
                if (result.get(a) <= arr[i][b]) {
                    merged.add(result.get(a++));
                } else {
                    merged.add(arr[i][b++]);
                }
            }
            while (a < result.size()) merged.add(result.get(a++));
            while (b < arr[i].length) merged.add(arr[i][b++]);
            result = merged;   // the merged list is the new result
        }
        return result;
    }
}

from typing import List

class Solution:
    def mergeKArrays(self, arr: List[List[int]], K: int) -> List[int]:
        # Holds everything merged so far. Starts empty.
        result: List[int] = []
        for i in range(K):
            # Merge the result with the next array, the same way merge sort merges two halves.
            merged: List[int] = []
            a, b = 0, 0
            while a < len(result) and b < len(arr[i]):
                if result[a] <= arr[i][b]:
                    merged.append(result[a])
                    a += 1
                else:
                    merged.append(arr[i][b])
                    b += 1
            while a < len(result):
                merged.append(result[a])
                a += 1
            while b < len(arr[i]):
                merged.append(arr[i][b])
                b += 1
            result = merged   # the merged list is the new result

        return result

export function mergeKArrays(arr: number[][], K: number): number[] {
    // Holds everything merged so far. Starts empty.
    let result: number[] = [];
    for (let i = 0; i < K; i++) {
        // Merge the result with the next array, the same way merge sort merges two halves.
        const merged: number[] = [];
        let a = 0, b = 0;
        while (a < result.length && b < arr[i].length) {
            if (result[a] <= arr[i][b]) {
                merged.push(result[a++]);
            } else {
                merged.push(arr[i][b++]);
            }
        }
        while (a < result.length) merged.push(result[a++]);
        while (b < arr[i].length) merged.push(arr[i][b++]);
        result = merged;   // the merged list is the new result
    }
    return result;
}

Complexity

Time O(N · K)Space O(N)

Merging the result (size up to N) with each of the K arrays costs O(N) per merge, so O(N · K) in total. It is correct and needs no heap, but it is still slower than it has to be when K is large.

Optimized approach

Idea

Start from brute force

Brute force sorts all N values, which throws away the fact that each array is already sorted. The arrays already did most of the ordering work.

Find the repeated work

Sorting compares values that are already in order inside each array. We only need to compare the front values across arrays, one at a time.

Define the state — what variables do I need?

heap: One entry per array that still has unused elements: (value, array number, index inside that array).
result: The elements output so far. It always holds the smallest values, in order.

Define validity

The smallest unused element overall is always the smallest of the first unused elements of the arrays, so the heap top is always the correct next output.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

For every non-empty array, push (its first element, array number, 0)

At the start, each array's first element is its only candidate. Empty arrays have no candidate, so they are skipped.

While the heap is not empty

Pop the top (v, i, j) and append v to the result

The top is the smallest candidate. Every element not yet output is at least as big as the candidate from its own array, so v is the next value in order.

After the pop, if j + 1 is still inside array i

Push (arr[i][j + 1], i, j + 1)

That array's new first unused element is now its only candidate. Pushing it keeps exactly one entry per array.

What does the current window add to the answer?

Each pop appends exactly one element. Every element is pushed once and popped once, so when the heap is empty the result holds all N elements in order.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> mergeKArrays(vector<vector<int>>& arr, int K) {
        // Heap entries: (value, which array it came from, its index inside that array).
        using Item = tuple<int, int, int>;
        // greater<> turns the heap into a MIN-heap: the smallest value sits on top.
        priority_queue<Item, vector<Item>, greater<Item>> pq;

        // One candidate per array: the first element of each non-empty array.
        for (int i = 0; i < K; i++) {
            if (!arr[i].empty()) pq.push(Item(arr[i][0], i, 0));
        }

        vector<int> result;
        while (!pq.empty()) {
            auto [value, i, j] = pq.top();
            pq.pop();
            result.push_back(value);
            // The array we just took from offers its next element.
            // The heap never holds more than one element per array, so it stays at most K big.
            if (j + 1 < (int)arr[i].size()) pq.push(Item(arr[i][j + 1], i, j + 1));
        }
        return result;
    }
};

import java.util.ArrayList;
import java.util.PriorityQueue;

class Solution {
    public ArrayList<Integer> mergeKArrays(int[][] arr, int K) {
        // Heap entries: [value, which array it came from, its index inside that array].
        // MIN-heap: the smallest value sits on top.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

        // One candidate per array: the first element of each non-empty array.
        for (int i = 0; i < K; i++) {
            if (arr[i].length > 0) {
                pq.offer(new int[]{arr[i][0], i, 0});
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            int[] item = pq.poll();
            int value = item[0];
            int i = item[1];
            int j = item[2];
            result.add(value);
            // The array we just took from offers its next element.
            // The heap never holds more than one element per array, so it stays at most K big.
            if (j + 1 < arr[i].length) {
                pq.offer(new int[]{arr[i][j + 1], i, j + 1});
            }
        }
        return result;
    }
}

import heapq
from typing import List, Tuple

class Solution:
    def mergeKArrays(self, arr: List[List[int]], K: int) -> List[int]:
        # Heap entries: (value, which array it came from, its index inside that array).
        # MIN-heap: the smallest value sits on top.
        pq: List[Tuple[int, int, int]] = []

        # One candidate per array: the first element of each non-empty array.
        for i in range(K):
            if arr[i]:
                heapq.heappush(pq, (arr[i][0], i, 0))

        result: List[int] = []
        while pq:
            value, i, j = heapq.heappop(pq)
            result.append(value)
            # The array we just took from offers its next element.
            # The heap never holds more than one element per array, so it stays at most K big.
            if j + 1 < len(arr[i]):
                heapq.heappush(pq, (arr[i][j + 1], i, j + 1))

        return result

class PriorityQueue<T> {
    private heap: T[] = [];
    constructor(private compare: (a: T, b: T) => number) {}

    push(val: T): void {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop(): T | undefined {
        if (this.heap.length === 0) return undefined;
        const top = this.heap[0];
        const bottom = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = bottom;
            this.bubbleDown(0);
        }
        return top;
    }

    peek(): T | undefined {
        return this.heap[0];
    }

    size(): number {
        return this.heap.length;
    }

    isEmpty(): boolean {
        return this.heap.length === 0;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const p = (idx - 1) >> 1;
            if (this.compare(this.heap[idx], this.heap[p]) < 0) {
                [this.heap[idx], this.heap[p]] = [this.heap[p], this.heap[idx]];
                idx = p;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.heap.length;
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.compare(this.heap[left], this.heap[smallest]) < 0) {
                smallest = left;
            }
            if (right < len && this.compare(this.heap[right], this.heap[smallest]) < 0) {
                smallest = right;
            }
            if (smallest !== idx) {
                [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

export function mergeKArrays(arr: number[][], K: number): number[] {
    // Heap entries: [value, which array it came from, its index inside that array].
    // MIN-heap: the smallest value sits on top.
    const pq = new PriorityQueue<[number, number, number]>((a, b) => a[0] - b[0]);

    // One candidate per array: the first element of each non-empty array.
    for (let i = 0; i < K; i++) {
        if (arr[i] && arr[i].length > 0) {
            pq.push([arr[i][0], i, 0]);
        }
    }

    const result: number[] = [];
    while (!pq.isEmpty()) {
        const [value, i, j] = pq.pop()!;
        result.push(value);
        // The array we just took from offers its next element.
        // The heap never holds more than one element per array, so it stays at most K big.
        if (j + 1 < arr[i].length) {
            pq.push([arr[i][j + 1], i, j + 1]);
        }
    }
    return result;
}

Complexity

Time O(N log K)Space O(K)

The heap holds at most K entries, so each push and pop costs O(log K). The output itself is O(N), which the problem asks for.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Copy every element into one list, then sort the whole list	O(N log N)	O(N)
Better	Merge the result with the next array, like merge sort's merge step	O(N · K)	O(N)
Optimal	Keep the first unused element of each array in a min-heap; pop the smallest, then push its successor	O(N log K)	O(K)

Why does this belong to this pattern?

Clues in the problem statement

“K sorted arrays”Each array is sorted, so only its first unused element can be the next output from it. That is why K candidates are enough.
“merge into one sorted array”At every step, take the smallest of the candidates → a min-heap of the front values.
“every element appears once”Each element is pushed and popped once, so the cost is N pushes and pops, not one per array.

K sorted lists+need the smallest current front each time+heap of K fronts→K-way Merge — Merge K sorted (heap with one front per list)

Merging two sorted arrays needs one comparison per step: the two fronts. With K arrays, the next value is the smallest of K fronts, so we keep a min-heap of K candidates. The key move is pop, then push that array's successor. Push nothing else. Merge K Sorted Lists uses the same heap on linked lists, and Sort a Nearly Sorted Array uses it with a window of k + 1 items.

Don't make this mistake

Pushing every element into the heap (pattern confusion)

✗ for (int i = 0; i < K; i++) for (int x = 0; x < (int)arr[i].size(); x++) pq.push(Item(arr[i][x], i, x));

✓ for (int i = 0; i < K; i++) if (!arr[i].empty()) pq.push(Item(arr[i][0], i, 0));

The output is still sorted, so this looks right. But the heap now starts with all 10 elements instead of 3. That is just heap sort, O(N log N), and it throws away the idea that each array offers one candidate at a time. Push only the first element of each array.

Comparator direction: priority_queue is a max-heap by default

✗ priority_queue<Item> pq;

✓ priority_queue<Item, vector<Item>, greater<Item>> pq;

On the dry run the heads are 2, 1 and 0. A max-heap pops 2 first, then keeps taking the largest head from each array. It outputs 2 6 9 1 5 8 0 3 4 7, which is not sorted. greater<> turns the heap into a min-heap.

Forgetting to push the successor

✗ auto [v, i, j] = pq.top(); pq.pop(); result.push_back(v); // nothing pushed for array i

✓ auto [v, i, j] = pq.top(); pq.pop(); result.push_back(v); if (j + 1 < (int)arr[i].size()) pq.push(Item(arr[i][j + 1], i, j + 1));

The heap only ever holds the first unused element of each array. Without the push, it empties after 3 pops. On the dry run the output would be just [0, 1, 2].

Reading the first element of an empty array

✗ for (int i = 0; i < K; i++) pq.push(Item(arr[i][0], i, 0));

✓ for (int i = 0; i < K; i++) if (!arr[i].empty()) pq.push(Item(arr[i][0], i, 0));

An empty array has no element 0. Reading it is undefined behaviour and often crashes. Check the size before reading the first element.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like K-way Merge translate into production architectures and low-level memory mechanics.

LLD Architecture