88. Merge Sorted Array

Merge Sorted Array (LeetCode 88) 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.

• NeetCode 250 · #27 of 250 · Two Pointers

How to solve Merge Sorted Array

Merge Sorted Array is a Merge Sorted Array In-Place problem, part of Array/Matrix Manipulation Patterns. Learn the merge sorted array technique starting from the end. Essential for space-efficient array merging in coding interviews.

Work towards the solution in these steps:

1. You can easily solve this problem if you simply think about two elements at a time rather than two arrays. We know that each of the individual arrays is sorted. What we don't know is how they will intertwine. Can we take a local decision and arrive at an optimal solution?
2. If you simply consider one element each at a time from the two arrays and make a decision and proceed accordingly, you will arrive at the optimal solution.

The reference solution runs in O(m + n) time and O(1) space.

The Merge Sorted Array solution and editorial walks through the full approach with reference code.

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) time and O(1) 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

• Array/Matrix Manipulation Patterns pattern guide
• Merge Sorted Array (In-place from End) subpattern
• The full DSA patterns 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:

• Add Binary — Easy, same pattern
• Add to Array-Form of Integer — Easy, same pattern
• Concatenation of Array — Easy, same pattern
• Contains Duplicate — Easy, same pattern
• Design HashSet — Easy, same pattern
• Diagonal Traverse — Medium, same pattern

Merge Sorted Array FAQ