Merge K Sorted Arrays

93.3k
0

Given K integer arrays sorted in non-decreasing order, merge every array into a single non-decreasing array.

Input arrays may have different lengths, contain duplicate or negative values, or be empty. The returned array must preserve every input occurrence.

Example 1

Input: arrays = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Explanation: All eight values appear in non-decreasing order, and both occurrences of 1 and 4 remain present.

Example 2

Input: arrays = [[], [-3, -1, -1], [], [2]]
Output: [-3, -1, -1, 2]
Explanation: Empty arrays add no values, while negative values and duplicate occurrences remain in the merged result.

Brute Force Approach

The easiest starting point ignores the sorted order inside each array. Every value can be copied into one result array, followed by a normal sort over the complete collection.

The idea is short and reliable, but full sorting repeats comparison work already completed inside the input arrays. Larger inputs make the unused sorted structure expensive.

Algorithm

  • Begin with an empty array named result, so copied values share one final storage area.

  • Visit each sorted array in input order, because every input occurrence must appear in the merged output.

  • Append every encountered value to result, preserving duplicates without requiring special handling.

  • Leave empty arrays unchanged during copying, because no value exists for insertion from an empty source.

  • Sort result in non-decreasing order, so the complete unsorted collection becomes a valid merged array.

  • Return result after sorting, because every input value now occupies the required global order.

Dry Run

merge-k-sorted-array brute

merge-k-sorted-array brute

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Merges all arrays by sorting every value.
vector<int> mergeKArrays(vector<vector<int>>& arrays) {
vector<int> result;
// Copy every value into one result array.
for (vector<int>& currentArray : arrays) {
for (int value : currentArray) {
result.push_back(value);
}
}
// Sort all copied values into global order.
sort(result.begin(), result.end());
return result;
}
};
// Driver code
int main() {
vector<vector<int>> arrays = {
{1, 4, 5}, {1, 3, 4}, {2, 6}
};
Solution obj;
vector<int> result = obj.mergeKArrays(arrays);
for (int value : result) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), copying processes N total values and sorting the combined array dominates the running time.

Space Complexity: O(N), the returned result stores all N values; sorting may also use language-dependent auxiliary memory within the same upper bound.

Better Approach

The sorted input order becomes useful through the familiar two-pointer merge for two arrays. A running result can merge with the next input array, so no full sort is required.

Each new merge is linear in the two participating lengths. Early values can still be copied many times as the running result grows, leaving a costly worst case for a large number of arrays.

Algorithm

  • Begin with an empty result, so the first input array can establish the initial sorted collection naturally.

  • Keep a helper for merging two sorted arrays, because two moving indices can always select the smaller available value.

  • Compare the current values from both helper inputs, appending the smaller value so the merged prefix remains sorted.

  • Prefer the first input during equality, because either equal value is valid and both occurrences still enter the result.

  • Append any remaining suffix after one input ends, because the untouched suffix is already sorted.

  • Merge each input array into result from left to right, because each round needs one sorted collection for the next merge.

  • Return the final result, because every round preserves sorted order and adds every value from one more array.

Dry Run

merge-k-sorted-array better

merge-k-sorted-array better

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
// Merges two sorted arrays with two pointers.
vector<int> mergeTwoArrays(
vector<int>& first,
vector<int>& second
) {
vector<int> merged;
int firstIndex = 0;
int secondIndex = 0;
// Compare both available front values.
while (firstIndex < first.size() &&
secondIndex < second.size()) {
// Smaller first value keeps sorted order.
if (first[firstIndex] <= second[secondIndex]) {
merged.push_back(first[firstIndex]);
firstIndex++;
} else {
merged.push_back(second[secondIndex]);
secondIndex++;
}
}
// Copy any remaining first-array suffix.
while (firstIndex < first.size()) {
merged.push_back(first[firstIndex]);
firstIndex++;
}
// Copy any remaining second-array suffix.
while (secondIndex < second.size()) {
merged.push_back(second[secondIndex]);
secondIndex++;
}
return merged;
}
public:
// Merges arrays one after another.
vector<int> mergeKArrays(vector<vector<int>>& arrays) {
vector<int> result;
// Add one sorted array during every round.
for (vector<int>& currentArray : arrays) {
result = mergeTwoArrays(result, currentArray);
}
return result;
}
};
// Driver code
int main() {
vector<vector<int>> arrays = {
{1, 4, 5}, {1, 3, 4}, {2, 6}
};
Solution obj;
vector<int> result = obj.mergeKArrays(arrays);
for (int value : result) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × K), early values can be copied during many sequential merges, producing the stated worst-case bound across K arrays and N total values.

Space Complexity: O(N), the running result and temporary merged array together store a linear number of values.

Optimal Approach

Only one candidate from each non-empty array matters at any moment: the smallest unmerged value from the array. Every later value in the same array is at least as large, so no later value needs consideration before the candidate.

A min-heap keeps at most K candidates and exposes the smallest candidate quickly. After removing a candidate, the next value from the same source array becomes eligible, creating a clean K-way merge.

Algorithm

  • Begin with an empty min-heap storing (value, array index, element index), so each candidate retains a path to the next source value.

  • Insert the first value from every non-empty array, because each first value is the smallest unmerged candidate from one source.

  • Remove the minimum heap entry, because the entry is no larger than any current candidate or any later source value.

  • Append the removed value to result, because the heap minimum preserves non-decreasing order.

  • Move to the next index in the removed entry's source array, preserving the source position after one value is consumed.

  • Insert the next source value only if the index remains valid, so empty suffixes never create invalid heap entries.

  • Repeat removal and replacement until the heap becomes empty, then return result because every source value has been consumed.

Dry Run

merge-k-sorted-array optimal

merge-k-sorted-array optimal

Solution

#include <bits/stdc++.h>
using namespace std;
struct Node {
int value;
int arrayIndex;
int elementIndex;
};
struct Compare {
// Gives smaller values higher heap priority.
bool operator()(Node first, Node second) {
return first.value > second.value;
}
};
class Solution {
public:
// Merges arrays with a min-heap.
vector<int> mergeKArrays(vector<vector<int>>& arrays) {
priority_queue<Node, vector<Node>, Compare> minHeap;
vector<int> result;
// Add one smallest candidate per non-empty array.
for (int arrayIndex = 0;
arrayIndex < arrays.size();
arrayIndex++) {
// Empty arrays have no valid heap candidate.
if (!arrays[arrayIndex].empty()) {
minHeap.push({
arrays[arrayIndex][0], arrayIndex, 0
});
}
}
// Consume the smallest available candidate.
while (!minHeap.empty()) {
Node current = minHeap.top();
minHeap.pop();
// Heap minimum is the next merged value.
result.push_back(current.value);
int nextIndex = current.elementIndex + 1;
// A valid next value replaces the consumed one.
if (nextIndex < arrays[current.arrayIndex].size()) {
minHeap.push({
arrays[current.arrayIndex][nextIndex],
current.arrayIndex,
nextIndex
});
}
}
return result;
}
};
// Driver code
int main() {
vector<vector<int>> arrays = {
{1, 4, 5}, {1, 3, 4}, {2, 6}
};
Solution obj;
vector<int> result = obj.mergeKArrays(arrays);
for (int value : result) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log K), each of the N values enters and leaves a heap containing at most one candidate from each of the K arrays.

Space Complexity: O(N + K), the returned result stores N values and the min-heap stores at most K candidates.

Interview follow-up Questions

Yes. Every approach processes each array according to the array's own length, so equal lengths are unnecessary.

Heap

Read Similar Blogs

Heap

Find K Pairs with Smallest Sums

Input: nums1 = [1, 7, 11] , nums2 = [2, 4, 6] , k = 3 Output: [[0, 0], [0, 1], [0, 2]] Explanation: Index-pairs [0, 0] , [0, 1] , and [0, 2] produce sums 3 , 5 , and 7 , so the three displayed inde...

61.1k
Heap

Introduction to Heap

Imagine an emergency room with several waiting patients. The patient needing the most urgent care is treated first, even if another patient arrived earlier. The next choice depends on...

72.8k
Heap

Meeting Rooms II

Given an array intervals , where every entry [start, end] represents one meeting, find the minimum number of conference rooms needed to hold every meeting without a scheduling conflict. An end time...

57.7k
Comments0