How to Solve Merge Two Sorted Arrays on LeetCode
The Merge Two Sorted Arrays problem is a standard interview question that checks your array handling and in-place update skills.
Problem Statement
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Assume nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Why This Problem Matters for Interviews
This problem:
- Validates your understanding of array indexing and in-place modifications
- Reinforces reverse traversal to avoid overwriting
- Models merging step of merge sort
Approaches to Merge Two Sorted Arrays
1. In-Place Merge from End (Optimal)
Start from the end, fill nums1 backwards.
Time Complexity: O(m + n)
Space Complexity: O(1)
def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
i, j, k = m - 1, n - 1, m + n - 1
while i >= 0 and j >= 0:
if nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 1
2. Merge and Sort
Simple but not in-place optimal.
Time Complexity: O((m + n) log (m + n))
Space Complexity: O(1) (if using nums1 only)
def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
nums1[m:] = nums2
nums1.sort()
Key Interview Talking Points
- Why reverse traversal prevents overwriting nums1
- Tradeoff between in-place and extra-sort methods
- Merging as a core of merge sort
- Handling empty arrays or all elements from one side
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| In-Place Merge | O(m + n) | O(1) |
| Merge and Sort | O((m + n) log(m+n)) | O(1) |
Pro Interview Tips
- Walk through in-place merge with pointer updates.
- Discuss time/space efficiency in interviews.
- Practice with test cases