Two Pointers — Merge Sorted Array
↗ LeetCode: Merge Sorted Array · Easy · pattern chapter →
Asked atMetaAmazonMicrosoftGoogleBloomberg
Merge nums2 into nums1 in-place; nums1 has size m+n with last n slots empty.
Example 1 — nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3 → [1,2,2,3,5,6]Example 2 — nums1=[1], m=1, nums2=[], n=0 → [1]
Constraints — nums1.length == m + n. Brute concat + sort is O((m+n) log(m+n)) — fine for 10² inputs, misses the point. In-place from-the-back three-pointer is O(m+n) = ~10⁶ pointer ops on real payload sizes.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Copy then sort
O((m+n) log(m+n)). Baseline.
Approach 2 — Backward two-pointer (canonical)
Insight. Fill from the back so we never overwrite an unread element.
java
void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
}Execution Trace
Complexity — Time O(m+n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Copy + sort | O((m+n) log) | O(m+n) | baseline |
| Fill from back | O(m+n) | O(1) | canonical |
When to use which
- In-place merge with buffer at back → fill from back.
- No buffer → allocate new array.
- Linked lists → same idea; see Merge Two Sorted Lists.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems