Solution: Merge Sorted Array
Let's solve the Merge Sorted Array problem using the K-way Merge pattern.
Statement
Given two sorted integer arrays, and , and the number of data elements in each array, and , implement a function that merges the second array into the first one. You have to modify in place.
Note: Assume that has a size equal to , meaning it has enough space to hold additional elements from .
Constraints:
nums1.length
nums2.length
-
nums1[i]
,nums2[j]
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
The naive approach here is to append the second array to the first—at a cost of —and then sort it using quick sort—at a cost of —for an overall time complexity of .
Optimized approach using k-way merge
Since we have two sorted arrays to merge, this problem is the simplest illustration of the k-way merge pattern.
With the k-way merge approach, we iterate over our given arrays using two pointers and merge them in place. The time complexity for this is , which is more efficient than the complexity of the naive approach.
We can solve this problem by comparing both arrays from the end and populating the result in the nums1
array. The slides below illustrate how we would like the algorithm to run:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.