Solution: Merge Sorted Array

Statement

Given two sorted integer arrays, nums1nums1 and nums2nums2, and the number of data elements in each array, mm and nn, implement a function that merges the second array into the first one. You have to modify nums1nums1 in place.

Note: Assume that nums1nums1 has a size equal to m+nm + n, meaning it has enough space to hold additional elements from nums2nums2.

Constraints:

  • nums1.length =m+n= m + n
  • nums2.length =n= n
  • 0m,n2000 \leq m, n \leq 200
  • 1m+n2001 \leq m + n \leq 200
  • 103-10^3 \leq nums1[i], nums2[j] 103\leq 10^3

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 list to the first—at a cost of O(n)O(n)—and then sort it using quick sort—at a cost of O((m+n)log(m+n))O((m + n) \log(m + n))—for an overall time complexity of O((m+n)log(m+n))O((m + n) \log(m + n)).

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 O(m+n)O(m + n), which is more efficient than the O((m+n)log(m+n))O((m + n) \log(m + n)) 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 80+ hands-on prep courses.