Solution: Merge Two Sorted Arrays

Let’s solve the Merge Two Sorted Arrays problem.

We'll cover the following

Statement

Given two integer arrays, nums1 and nums2, of size mm and nn, respectively, sorted in nondecreasing order. Merge nums1 and nums2 into a single array sorted in nondecreasing order.

Constraints:

  • 0≤m,n≤2000\leq m, n \leq 200

  • 1≤m+n≤2001\leq m + n \leq 200

  • −103≤-10^3 \leq nums1[i] , nums2[i] ≤103\leq 10^3

Solution 1: Creating a new array and using three pointers

Since we have two arrays, nums1 and nums2, to merge, we start by creating a new empty array result of length equal to the sum of the length of nums1 and nums2. This array will be filled with all the elements of both arrays in sorted order and returned. The following are the further steps of the algorithm:

  1. Initialize three pointers, p1, p2, and p3, pointing to the start of nums1, nums2, and result, respectively.

  2. Traverse both arrays until the end of either nums1 and nums2 is reached.

  3. While traversing, compare the elements of nums1 and nums2, pointed by p1 and p2, respectively. Check whether the element pointed by p1 or p2 is smaller.

    1. If the element pointed by p1 is smaller, store this element at the position pointed by p3. Also, increment p1 and p3 by 1.

    2. Otherwise, if the element pointed by p2 is smaller, store this element at the position pointed by p3. Also, increment p2 and p3 by 1.

  4. After the traversal, append the rest of the elements in any of the array to result.

The following illustrations demonstrate the algorithm:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.