How do you approach Merge Sorted Array?

Use two pointers, one for each array.

What is the time complexity of Merge Sorted Array?

Time complexity: O(n + m) - where n and m are the lengths of the two arrays. Space complexity: O(n + m) - for the result array.

What are common mistakes on Merge Sorted Array?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

gitGood.dev

← Back to problems

Merge Sorted Array

EasyAlgorithms

Description

Given two sorted integer arrays nums1 and nums2, merge them into a single sorted array and return the result.

The arrays are sorted in non-decreasing order.

Example 1

Input: nums1 = [1, 2, 3], nums2 = [2, 5, 6]

Output: [1, 2, 2, 3, 5, 6]

Example 2

Input: nums1 = [1], nums2 = []

Output: [1]

Example 3

Input: nums1 = [], nums2 = [1]

Output: [1]

Constraints

- 0 <= nums1.length, nums2.length <= 200 - -10^9 <= nums1[i], nums2[i] <= 10^9 - Both nums1 and nums2 are sorted in non-decreasing order.

Merge Sorted Array: approach, complexity and pitfalls

An easy two pointers problem, graded against 7 test cases (4 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

Use two pointers, one for each array.
Compare elements at both pointers and add the smaller one to the result.
Don't forget to handle the remaining elements when one array is exhausted.

The optimal approach

Show the approach: Two Pointers

Use two pointers starting at the beginning of each array. Compare the elements at both pointers, add the smaller one to the result, and advance that pointer. When one array is exhausted, append the remaining elements from the other.

Time: O(n + m) - where n and m are the lengths of the two arrays
Space: O(n + m) - for the result array

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.

← Back to problems

Merge Sorted Array

EasyAlgorithms

Description

Given two sorted integer arrays nums1 and nums2, merge them into a single sorted array and return the result.

The arrays are sorted in non-decreasing order.

Example 1

Input: nums1 = [1, 2, 3], nums2 = [2, 5, 6]

Output: [1, 2, 2, 3, 5, 6]

Example 2

Input: nums1 = [1], nums2 = []

Output: [1]

Example 3

Input: nums1 = [], nums2 = [1]

Output: [1]

Constraints

- 0 <= nums1.length, nums2.length <= 200 - -10^9 <= nums1[i], nums2[i] <= 10^9 - Both nums1 and nums2 are sorted in non-decreasing order.

Merge Sorted Array: approach, complexity and pitfalls

An easy two pointers problem, graded against 7 test cases (4 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

Use two pointers, one for each array.
Compare elements at both pointers and add the smaller one to the result.
Don't forget to handle the remaining elements when one array is exhausted.

The optimal approach

Show the approach: Two Pointers

Time: O(n + m) - where n and m are the lengths of the two arrays
Space: O(n + m) - for the result array

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.