Solution: Merge Sorted Array

Statement#

Given two sorted integer arrays, $nums1$ and $nums2$, and the number of data elements in each array, $m$ and $n$, implement a function that merges the second array into the first one. You have to modify $nums1$ in place.

Note: Assume that $nums1$ has a size equal to $m + n$, meaning it has enough space to hold additional elements from $nums2$.

Constraints:

• nums1.length $= m + n$
• nums2.length $= n$
• $0 \leq m, n \leq 200$
• $1 \leq m + n \leq 200$
• $-10^3 \leq$ nums1[i], nums2[j] $\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)$—and then sort it using quick sort—at a cost of $O((m + n) \log(m + n))$—for an overall time complexity of $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)$, which is more efficient than the $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:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

First, we initialize two pointers, p1 and p2, that point to the last element of each array. p1 is initialized to m - 1, the index of the last data element in nums1, and p2 is initialized to n - 1, the index of the last data element in nums2.

Next, we initialize another pointer called p, which points to the m + n - 1 index of nums1. We use the pointer p to traverse the nums1 array from the end. If the value at p1 is greater than the value at p2, the result at p is equal to the value at p1. We then decrement p1 to move it one element back.

If the value at p1 is less than the value at p2, the result at p is set equal to the value at p2. We decrement the pointer for the list that the entry was copied from.

The traversal continues until nums2 is merged with nums1.

Just the code#

Here’s the complete solution to this problem:

Solution summary#

To recap, the solution to this problem can be divided into the following parts:

1. Initialize two pointers that point to the last data elements in both arrays.
2. Initialize a third pointer that points to the last index of $nums1$.
3. Traverse $nums1$ from the end using the third pointer and compare the values corresponding to the first two pointers.
4. Place the larger of the two values at the third pointer’s index.
5. Repeat the process until the two arrays are merged.

Time complexity#

The time complexity is $O(n + m)$, where $n$ and $m$ are the counts of initialized elements in the two arrays.

Space complexity#

The space complexity is $O(1)$ because we only use the space required for three indices.