Merge Three Sorted Arrays
Design an algorithm to merge three sorted arrays into a single sorted array. This is similar to the LeetCode question 'Merge Sorted Arrays' but involves three arrays instead of two.
Asked at:
Meta
DESCRIPTION
Design an algorithm to merge three sorted arrays into a single sorted array. This is similar to the LeetCode question 'Merge Sorted Arrays' but involves three arrays instead of two.
Input:
arr1 = [1, 4, 7], arr2 = [2, 5, 8], arr3 = [3, 6, 9]
Output:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Explanation: Merging three sorted arrays by repeatedly picking the smallest available element from the front of each array
Constraints:
- 0 <= arr1.length, arr2.length, arr3.length <= 10^4
- -10^9 <= arr1[i], arr2[i], arr3[i] <= 10^9
- arr1, arr2, and arr3 are sorted in non-decreasing order
- Total number of elements across all arrays <= 10^4
Understanding the Problem
Let's understand what we're being asked to do. We have three sorted arrays like arr1 = [1, 4, 7], arr2 = [2, 5, 8], and arr3 = [3, 6, 9], and we need to merge them into a single sorted array [1, 2, 3, 4, 5, 6, 7, 8, 9].
Tracing through manually: we'd compare the first elements of each array (1, 2, 3), pick the smallest (1), then compare the next available elements (4, 2, 3), pick 2, and so on.
Important constraint: Each input array is already sorted in ascending order. We're not sorting random data - we're merging pre-sorted sequences!
Edge cases to consider: What if one array is empty? What if all arrays have the same elements? What if arrays have vastly different lengths? What if we had K arrays instead of just three?
Brute Force Approach
The simplest approach is to concatenate all three arrays into one large array, then sort the combined array. This ignores the fact that the input arrays are already sorted. While easy to implement (just use a built-in sort function), this approach doesn't leverage the sorted property and performs unnecessary comparisons.
def merge_three_sorted_arrays(arr1, arr2, arr3):"""Brute force approach: Concatenate all three arrays and sort.This ignores the fact that input arrays are already sorted.Time: O(n log n) where n is total elementsSpace: O(n) for the merged array"""# Concatenate all three arrays into onemerged = arr1 + arr2 + arr3# Sort the combined array (inefficient - doesn't use sorted property)merged.sort()# Return the sorted resultreturn merged
Start merge three sorted arrays (brute force)
0 / 12
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n log n) Where n is the total number of elements across all three arrays. Sorting the concatenated array takes O(n log n) time
Space Complexity: O(n) We need O(n) space to store the concatenated array and the result array
Building Intuition
At each step, the next smallest element in the final merged array must be the smallest of the current front elements from all three arrays.
If we always pick the minimum among the three candidates (one from each array), we maintain sorted order in the result.
Instead of comparing every element with every other element (which would be very slow), we only need to compare the current candidates from each array.
This is much more efficient because we're leveraging the fact that each array is already sorted - we don't need to look ahead in any array.
Imagine three people, each holding a sorted deck of cards face-up. You're building a single sorted pile.
At each step, you look at the top card from each person's deck (the three visible cards), pick the smallest one, and add it to your pile. Then that person reveals their next card.
You never need to look at cards deeper in anyone's deck - the top cards are always the smallest remaining in each deck. This is the key insight for merging sorted sequences efficiently.
Common Mistakes
Optimal Solution
The optimal approach uses a min-heap (priority queue) to efficiently track the smallest available element across all three arrays. Initialize the heap with the first element from each array (along with array index and element index). Repeatedly extract the minimum element from the heap, add it to the result, and insert the next element from that same array into the heap. This ensures we always pick the globally smallest available element in O(log k) time, where k is the number of arrays.
import heapqdef merge_three_sorted_arrays(arr1, arr2, arr3):"""Merge three sorted arrays using a min-heap.Time: O(n log k) where n is total elements, k=3 arrays.Space: O(k) for heap + O(n) for result."""# Initialize result array and min-heapresult = []min_heap = []# Add first element from each non-empty array to heap# Heap stores tuples: (value, array_index, element_index)if arr1:heapq.heappush(min_heap, (arr1[0], 0, 0))if arr2:heapq.heappush(min_heap, (arr2[0], 1, 0))if arr3:heapq.heappush(min_heap, (arr3[0], 2, 0))# Arrays reference for easy accessarrays = [arr1, arr2, arr3]# Process heap until emptywhile min_heap:# Extract minimum elementvalue, array_idx, elem_idx = heapq.heappop(min_heap)# Add to resultresult.append(value)# If current array has more elements, add next to heapnext_idx = elem_idx + 1if next_idx < len(arrays[array_idx]):next_value = arrays[array_idx][next_idx]heapq.heappush(min_heap, (next_value, array_idx, next_idx))return result
Start merging three sorted arrays
0 / 65
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n log k) Where n is the total number of elements and k is the number of arrays (3 in this case). Each of the n elements is inserted and extracted from the heap once, and each heap operation takes O(log k) time
Space Complexity: O(k) The heap stores at most k elements at any time (one candidate from each array), plus O(n) for the result array
What We've Learned
- Min-heap for K-way merge: When merging K sorted arrays (K≥2), use a min-heap of size K to track the smallest unprocessed element from each array - this reduces the problem from comparing all elements to just extracting the minimum K times, making it scalable beyond just 2-3 arrays.
- Tuple storage pattern: Store (value, array_index, element_index) tuples in your heap to track both the element's value and its origin - this allows you to know which array to pull the next element from after each extraction without losing context.
- Time complexity advantage: The heap approach achieves O(N log K) where N is total elements and K is number of arrays, compared to O(N*K) for naive pairwise comparison - as K grows, the logarithmic factor becomes crucial for performance.
- Index boundary pitfall: Always check if element_index + 1 < len(array) before pushing the next element from an array into the heap - forgetting this check causes index-out-of-bounds errors when an array is exhausted, especially with arrays of different lengths.
- K-way merge generalization: This heap-based pattern extends to merging K sorted linked lists, finding the Kth smallest element in K sorted arrays, and external sorting of large datasets - recognize any problem involving "multiple sorted sequences" as a K-way merge candidate.
- Space-time tradeoff insight: The heap uses O(K) extra space regardless of total array size, making it memory-efficient for large datasets - this is why external merge sort uses this technique to merge file chunks that don't fit in memory.
Related Concepts and Problems to Practice
hard
This problem is directly analogous to merging three sorted arrays. It uses a min-heap to efficiently merge K sorted linked lists by always selecting the smallest element, which is the exact same pattern needed for merging multiple sorted arrays.
medium
This problem teaches heap manipulation and the concept of maintaining ordered elements efficiently. The skills of using a heap to track and extract elements in sorted order directly apply to merging sorted arrays where you need to repeatedly find the minimum element.
Test Your Understanding
Why is heap the right data structure for this problem?
heap provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid November, 2025
Meta
Senior
Early November, 2025
Meta
Senior
Late October, 2025
Meta
Senior
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.