Introduction

Merging two sorted arrays means combining their elements into a single array while maintaining sorted order.

Because both input arrays are already sorted, we can use the Two Pointer technique to merge them efficiently.

Problem Statement

Given two sorted arrays nums1 and nums2, merge them into a single sorted array.

The resulting array should contain all elements from both arrays in sorted order.

Example

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

Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Constraints

  • Both arrays are sorted in ascending order.
  • 0 ≤ nums1.length
  • 0 ≤ nums2.length
  • Elements can be positive, negative, or zero.
  • Duplicate elements may exist.

Approach 1: Brute Force

Explanation

The simplest approach is to combine both arrays into a single array and then sort the complete array.

The process is:

  1. Copy all elements from the first array.
  2. Copy all elements from the second array.
  3. Sort the combined array.

This approach is simple but ignores the fact that both input arrays are already sorted.

Steps

  1. Create an empty result array.
  2. Add all elements from the first array.
  3. Add all elements from the second array.
  4. Sort the result.
  5. Return the sorted array.

Dry Run

nums1 = [1, 3, 5]nums2 = [2, 4, 6]

Combine:
[1, 3, 5, 2, 4, 6]

Sort:
[1, 2, 3, 4, 5, 6]

Final Result:
[1, 2, 3, 4, 5, 6]

Brute Force Code

Complexity Analysis

Let n be the size of the first array and m be the size of the second array.

Time Complexity: O((n + m) log(n + m))

Space Complexity: O(n + m)

Approach 2: Optimized Solution Using Two Pointers

Explanation

Since both arrays are already sorted, there is no need to sort them again.

We use two pointers:

  • One pointer for the first array.
  • One pointer for the second array.

Compare the elements at both pointers.

The smaller element is added to the result, and that pointer moves forward.

When one array is completely processed, add the remaining elements from the other array.

Steps

  1. Initialize i = 0 for the first array.
  2. Initialize j = 0 for the second array.
  3. Compare nums1[i] and nums2[j].
  4. Add the smaller element to the result.
  5. Move the corresponding pointer.
  6. Continue while both arrays contain elements.
  7. Add the remaining elements from either array.
  8. Return the merged array.

Dry Run

nums1 = [1, 3, 5]
nums2 = [2, 4, 6]

i = 0
j = 0
Compare:
1 and 2
1 is smaller
Result = [1]

i = 1
Compare:
3 and 2
2 is smaller
Result = [1, 2]

j = 1
Compare:
3 and 4
3 is smaller
Result = [1, 2, 3]

i = 2
Compare:
5 and 4
4 is smaller
Result = [1, 2, 3, 4]

j = 2
Compare:
5 and 6
5 is smaller
Result = [1, 2, 3, 4, 5]

i = 3
First array is finished.
Add remaining element:
6

Final Result:
[1, 2, 3, 4, 5, 6]

Optimized Code

Complexity Analysis

Time Complexity: O(n + m)

Space Complexity: O(n + m) for the resulting merged array.

Edge Cases

  • One array is empty.
  • Both arrays are empty.
  • One array contains only one element.
  • Both arrays contain duplicate values.
  • All elements of the first array are smaller.
  • All elements of the second array are smaller.
  • Both arrays contain negative values.

Why This Problem is Important

Merging sorted arrays is a fundamental technique used in Merge Sort and many other sorting and searching problems.

The two-pointer approach demonstrates how sorted data can be processed without repeatedly sorting it.

Real-World Applications

Merging sorted data is useful for:

  • Combining sorted database results.
  • Merging log files.
  • Combining sorted datasets.
  • External sorting.
  • Merging search results.
  • Processing data streams.

Common Mistakes

  • Sorting the arrays again even though they are already sorted.
  • Forgetting to process the remaining elements.
  • Moving both pointers after every comparison.
  • Using the wrong comparison condition.
  • Forgetting that duplicate elements should also be included.

Interview Tips

  • Recognize immediately that both arrays are already sorted.
  • Use two pointers instead of sorting again.
  • Always process the remaining elements after one array is exhausted.
  • Explain why each element is processed only once.
  • Connect this technique to the merge step of Merge Sort.

Related Questions

  • Merge Sort
  • Merge Overlapping Intervals
  • Count Inversions in an Array
  • Sort an Array of 0s, 1s and 2s
  • Merge K Sorted Arrays

Final Takeaway

The brute-force approach combines both arrays and sorts the complete result, taking O((n + m) log(n + m)) time.

The optimized Two Pointer approach takes advantage of the fact that both arrays are already sorted and merges them in O(n + m) time.

Key Idea: Compare the current elements of both sorted arrays, take the smaller one, and move that pointer forward.