Merge Sorted Array

Merge Sorted Array is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Merge Sorted Array (In-place from End) subpattern.

Problem statement

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and []. The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

- nums1.length == m + n

- nums2.length == n

- 0 <= m, n <= 200

- 1 <= m + n <= 200

- -109 <= nums1[i], nums2[j] <= 109

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Topics and companies

Topics: Array, Two Pointers, Sorting.

Reported in interviews at Facebook, Microsoft, Amazon, Bloomberg, Walmart Labs, IBM, Oracle, Apple, LinkedIn, Goldman Sachs, Yandex, Wish.

How to practise Merge Sorted Array on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m + n): Each element from nums1 and nums2 is processed exactly once in a single pass from the end. time and O(1): The merge is performed in-place using only a constant number of extra variables. space.

Open Merge Sorted Array in the code editor, or read the Merge Sorted Array editorial for a worked solution with its approach and complexity analysis.

Where Merge Sorted Array sits in the DSA pattern sheet

Problems related to Merge Sorted Array

Other problems that use the same Merge Sorted Array (In-place from End) and Array/Matrix Manipulation Patterns techniques:

Preparing this workspace.