Log inSign up
easyLeetCodeNot Started

Merge Sorted Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Standard 6-element Merge:

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 to merge are [1, 2, 3] and [2, 5, 6]. The result of the merge is [1, 2, 2, 3, 5, 6] stored directly in nums1.

Example 2 · nums2 is Empty (n = 0):

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: nums2 has 0 elements, so nums1 is already merged and remains [1].

Example 3 · nums1 is Initially Empty (m = 0):

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: nums1 has 0 valid elements. nums2's element 1 is copied into nums1, resulting in [1].

Constraints:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Two Pointers technique
  • Understanding the merge step of Merge Sort
  • In-place array manipulation without overwriting active data

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why forward two pointers overwrites elements in nums1 and how reverse pointers solves this.
  • Master three-pointer backward traversal: p1 = m - 1, p2 = n - 1, and p = m + n - 1.
  • Handle the crucial edge case where elements remain in nums2 after p1 < 0.
  • Write clean, robust in-place solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Two already sorted arrays need to be merged into one sorted collection.
  • The destination array has extra allocated capacity at the END.
  • Must be performed in-place with O(1) auxiliary space.

Algorithmic Decision Tree:

  • Whenever extra buffer exists at the tail of an array: fill from back-to-front (reverse two pointers) so you never overwrite unvisited elements.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Brute Force — Append & Sort

Intuition

Directly copy all n elements of nums2 into the tail of nums1 starting at index m, then sort the combined array.

Algorithm

  1. Loop i from 0 to n - 1:
  2. nums1[m + i] = nums2[i].
  3. Sort nums1 in ascending order.

Brute force — concatenate and sort

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
The zero-filled suffix is capacity, not input data
Visual state
Values and pointers at this exact step
array
S
1
2
3
0
0
0
0
1
2
3
4
5
Variables at this step
validNums1
3
nums2
[2,5,6]
Check / comparison
Only the first m=3 cells of nums1 are valid.
Decision / next transition
Append nums2 to the valid prefix.
Why this step matters

The zero-filled suffix is capacity, not input data.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Brute Force: Copy nums2 to end of nums1 and sort
7void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
8 for (int i = 0; i < n; i++) {
9 nums1[m + i] = nums2[i];
10 }
11 sort(nums1.begin(), nums1.end());
12}
13
14int main() {
15 vector<int> nums1 = {1, 2, 3, 0, 0, 0};
16 vector<int> nums2 = {2, 5, 6};
17 merge(nums1, 3, nums2, 3);
18
19 cout << "Output: [";
20 for (size_t i = 0; i < nums1.size(); i++) {
21 cout << nums1[i] << (i + 1 < nums1.size() ? ", " : "");
22 }
23 cout << "]" << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Approach 1: Brute Force — Append & Sort.
  • Space complexity: O(1) — Space complexity for Approach 1: Brute Force — Append & Sort.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Better — Forward Two Pointers (Auxiliary Buffer)

Intuition

Make a copy of the first m elements of nums1, then merge the copy and nums2 into nums1 from front to back.

Algorithm

  1. Create a copy nums1Copy of the first m elements of nums1.
  2. Set p1 = 0, p2 = 0, and p = 0.
  3. While p1 < m and p2 < n:
  4. If nums1Copy[p1] <= nums2[p2], nums1[p++] = nums1Copy[p1++].
  5. Else nums1[p++] = nums2[p2++].
  6. Copy remaining elements from nums1Copy or nums2 into nums1.

Better — merge into a temporary array

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
The smaller front value is the next merged value
Visual state
Values and pointers at this exact step
array
S
1
2
3
0
0
0
0
1
2
3
4
5
Variables at this step
i
0
j
0
k
0
temp
[1]
Check / comparison
i=0 and j=0 compare 1 and 2.
Decision / next transition
Copy 1 to temporary output.
Why this step matters

The smaller front value is the next merged value.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Better: Forward Two Pointers with auxiliary copy
6void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
7 vector<int> nums1Copy(nums1.begin(), nums1.begin() + m);
8
9 int p1 = 0, p2 = 0, p = 0;
10
11 while (p1 < m && p2 < n) {
12 if (nums1Copy[p1] <= nums2[p2]) {
13 nums1[p++] = nums1Copy[p1++];
14 } else {
15 nums1[p++] = nums2[p2++];
16 }
17 }
18
19 while (p1 < m) nums1[p++] = nums1Copy[p1++];
20 while (p2 < n) nums1[p++] = nums2[p2++];
21}
22
23int main() {
24 vector<int> nums1 = {1, 2, 3, 0, 0, 0};
25 vector<int> nums2 = {2, 5, 6};
26 merge(nums1, 3, nums2, 3);
27
28 cout << "Output: [";
29 for (size_t i = 0; i < nums1.size(); i++) {
30 cout << nums1[i] << (i + 1 < nums1.size() ? ", " : "");
31 }
32 cout << "]" << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Approach 2: Better — Forward Two Pointers (Auxiliary Buffer).
  • Space complexity: O(N) — Space complexity for Approach 2: Better — Forward Two Pointers (Auxiliary Buffer).

3. Optimal — Reverse Three Pointers (In-Place O(1) Space)

Intuition

Place pointers at the end of valid nums1 elements (m - 1), end of nums2 (n - 1), and end of the total buffer (m + n - 1). Fill largest values backwards.

Algorithm

  1. Initialize p1 = m - 1 (last valid element in nums1).
  2. Initialize p2 = n - 1 (last element in nums2).
  3. Initialize p = m + n - 1 (last write index in nums1).
  4. While p2 >= 0:
  5. If p1 >= 0 and nums1[p1] > nums2[p2]:
  6. nums1[p] = nums1[p1].
  7. p1--.
  8. Else:
  9. nums1[p] = nums2[p2].
  10. p2--.
  11. p--.

Optimal — merge backward in place

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
The largest remaining value belongs at the last free index
Visual state
Values and pointers at this exact step
array
S
1
2
3
0
0
0
0
1
2
3
4
5
Variables at this step
i
2
j
1
k
4
Check / comparison
i=2, j=2, k=5; compare 3 and 6.
Decision / next transition
Write 6 at index 5.
Why this step matters

The largest remaining value belongs at the last free index.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Optimal: Reverse Three Pointers in O(M + N) time and O(1) space
6void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
7 int p1 = m - 1; // Pointer for last valid element in nums1
8 int p2 = n - 1; // Pointer for last element in nums2
9 int p = m + n - 1; // Write pointer at end of nums1
10
11 // While there are elements to merge from nums2
12 while (p2 >= 0) {
13 if (p1 >= 0 && nums1[p1] > nums2[p2]) {
14 nums1[p] = nums1[p1];
15 p1--;
16 } else {
17 nums1[p] = nums2[p2];
18 p2--;
19 }
20 p--;
21 }
22}
23
24int main() {
25 vector<int> nums1 = {1, 2, 3, 0, 0, 0};
26 vector<int> nums2 = {2, 5, 6};
27 merge(nums1, 3, nums2, 3);
28
29 cout << "Output: [";
30 for (size_t i = 0; i < nums1.size(); i++) {
31 cout << nums1[i] << (i + 1 < nums1.size() ? ", " : "");
32 }
33 cout << "]" << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Approach 3: Optimal — Reverse Three Pointers (In-Place O(1) Space).
  • Space complexity: O(1) — Space complexity for Approach 3: Optimal — Reverse Three Pointers (In-Place O(1) Space).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Append & SortO((M + N) log (M + N))O(1) auxiliaryVery easy 2-line code.Baseline only.
2.Forward Two PointersO(M + N)O(M)Natural intuition from Merge Sort.Good step; interviewer will ask to remove the O(M) memory.
3.Reverse Three PointersOptimalO(M + N)O(1)Optimal linear time, strictly O(1) space, no overwritten data.Optimal gold standard.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • nums1 is Initially Empty (m = 0) — Input: nums1 = [0], m = 0, nums2 = [1], n = 1, Expected: [1] — p1 starts at -1. Loop must properly copy nums2 elements into nums1 without failing the p1 >= 0 check.
  • nums2 is Empty (n = 0) — Input: nums1 = [1], m = 1, nums2 = [], n = 0, Expected: [1] — p2 starts at -1, so loop terminates immediately. nums1 remains unmodified [1].
  • All Elements in nums2 are Smaller than nums1 — Input: nums1 = [4, 5, 6, 0, 0, 0], m = 3, nums2 = [1, 2, 3], n = 3, Expected: [1, 2, 3, 4, 5, 6] — All 3 elements of nums1 move to indices 3, 4, 5 first; then elements of nums2 fill indices 0, 1, 2.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the Why — Explain why backward merge avoids extra space: 'Because the empty buffer is at the back, writing from back to front guarantees we never overwrite unread elements in nums1.'
  2. Loop Condition Cleanliness — Loop while (p2 >= 0). Explain to the interviewer that if p2 < 0, any remaining elements in nums1 are already in their correct places and require no further work.
  3. Complexity Summary — Conclude clearly: 'Time complexity is O(m + n) single-pass and auxiliary space complexity is strictly O(1).'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Merge Sorted Array?

2.Why is the brute force approach suboptimal for large inputs in Merge Sorted Array?

3.Which data structure or technique enables the optimal solution for Merge Sorted Array?

Back to DSA Sheet