Skip to main content
CodePeetCodePeet
CodePeet 250

Merge Sorted Array

EASYProblemSolveExternal Links

Description

You are given two integer arrays nums1 and nums2, both sorted in non-decreasing order. You are also given two integers m and n, representing the number of meaningful elements in nums1 and nums2 respectively.

Your task is to merge nums2 into nums1 so that nums1 becomes a single sorted array in non-decreasing order.

Here is the catch: nums1 already has enough space allocated at the end to hold all elements from nums2. Specifically, nums1 has a length of m + n, where the first m positions contain the actual elements and the last n positions are filled with zeros (placeholders). You must perform the merge in-place inside nums1 — do not return a new array.

Examples

Example 1

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 meaningful elements of nums1 are [1, 2, 3] and nums2 is [2, 5, 6]. Merging them in sorted order gives [1, 2, 2, 3, 5, 6]. This result is stored directly inside nums1.

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0

Output: [1]

Explanation: nums2 is empty, so there is nothing to merge. nums1 remains [1].

Example 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1

Output: [1]

Explanation: nums1 has no meaningful elements (m = 0). The only element comes from nums2. We copy 1 into nums1, giving [1].

Constraints

  • nums1.length == m + n
  • nums2.length == n
  • 0 ≤ m, n ≤ 200
  • 1 ≤ m + n ≤ 200
  • -10^9 ≤ nums1[i], nums2[j] ≤ 10^9

Editorial

Brute Force

Intuition

The simplest idea is to ignore the fact that both arrays are already sorted and just combine them, then sort the result.

Since nums1 has extra space at the end (filled with zeros), we can copy all elements of nums2 into those trailing positions of nums1. After copying, nums1 contains all the elements we need — but in no particular order. We then sort the entire nums1 array to get the final merged sorted result.

Think of it like having two sorted stacks of exam papers. Instead of carefully interleaving them, you dump one pile on top of the other and then sort the combined pile from scratch. It works, but you are throwing away the information that each pile was already sorted.

Step-by-Step Explanation

Let's trace through with nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3:

Step 1: Start with nums1 = [1, 2, 3, 0, 0, 0]. The first 3 elements are meaningful, the last 3 are placeholders.

Step 2: Copy nums2[0] = 2 into nums1[3]. nums1 becomes [1, 2, 3, 2, 0, 0].

Step 3: Copy nums2[1] = 5 into nums1[4]. nums1 becomes [1, 2, 3, 2, 5, 0].

Step 4: Copy nums2[2] = 6 into nums1[5]. nums1 becomes [1, 2, 3, 2, 5, 6].

Step 5: Now all elements are in nums1, but not fully sorted. Sort nums1.

Step 6: After sorting, nums1 = [1, 2, 2, 3, 5, 6]. Done.

Brute Force — Copy Then Sort — Watch how we first copy all elements of nums2 into the trailing slots of nums1, then sort the entire array to get the merged result.

Algorithm

  1. Copy each element of nums2 into the trailing positions of nums1 (positions m, m+1, ..., m+n-1)
  2. Sort the entire nums1 array
  3. The merge is complete — nums1 now contains all elements in sorted order

Code

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        for i in range(n):
            nums1[m + i] = nums2[i]
        nums1.sort()
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

Complexity Analysis

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

Copying n elements takes O(n) time. Sorting the combined array of m + n elements takes O((m + n) log(m + n)) time, which dominates. We discard the existing sorted order and re-sort from scratch.

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

The copy step uses O(1) extra space. The sorting algorithm (e.g., quicksort/introsort) uses O(log(m + n)) space for the recursion stack. No additional arrays are allocated.

Why This Approach Is Not Efficient

The brute force approach sorts the entire array from scratch, costing O((m + n) log(m + n)) time. This completely ignores the valuable information that both nums1 and nums2 are already sorted.

When two arrays are already sorted, we can merge them in a single pass — just like the merge step of merge sort — by comparing front elements and picking the smaller one each time. This takes only O(m + n) time.

The key question becomes: can we take advantage of the sorted order to avoid the logarithmic overhead of a full sort? The answer is yes — using two pointers.

Better Approach - Two Pointer Merge with Extra Array

Intuition

Since both arrays are sorted, we can merge them efficiently by using two pointers — one for each array. We compare the elements at the two pointers and always pick the smaller one, placing it into a temporary result array. After one array is exhausted, we copy the remaining elements from the other.

Imagine two lines of students sorted by height. To merge them into one sorted line, you look at the front person in each line, pick the shorter one and place them next in the combined line, then repeat. You never need to go backwards because each line is already sorted.

This approach uses O(m + n) extra space for the temporary array, which we then copy back into nums1.

Step-by-Step Explanation

Let's trace through with nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3:

Step 1: Initialize pointers: i = 0 (for nums1), j = 0 (for nums2). Create empty temporary array.

Step 2: Compare nums1[0] = 1 vs nums2[0] = 2. 1 ≤ 2, so pick 1. temp = [1]. Advance i to 1.

Step 3: Compare nums1[1] = 2 vs nums2[0] = 2. 2 ≤ 2, so pick nums1's 2. temp = [1, 2]. Advance i to 2.

Step 4: Compare nums1[2] = 3 vs nums2[0] = 2. 3 > 2, so pick 2 from nums2. temp = [1, 2, 2]. Advance j to 1.

Step 5: Compare nums1[2] = 3 vs nums2[1] = 5. 3 ≤ 5, so pick 3. temp = [1, 2, 2, 3]. Advance i to 3. i has reached m, so nums1 is exhausted.

Step 6: Copy remaining nums2 elements: 5 and 6. temp = [1, 2, 2, 3, 5, 6].

Step 7: Copy temp back into nums1. nums1 = [1, 2, 2, 3, 5, 6]. Done.

Two Pointer Merge with Temporary Array — Watch two pointers walk through nums1 and nums2 simultaneously, always picking the smaller front element and placing it into a growing temporary result.

Algorithm

  1. Initialize pointer i = 0 for nums1 and j = 0 for nums2
  2. Create a temporary array of size m + n
  3. While both i < m and j < n:
    • If nums1[i] ≤ nums2[j], append nums1[i] to temp and increment i
    • Otherwise, append nums2[j] to temp and increment j
  4. Copy any remaining elements from nums1 (while i < m)
  5. Copy any remaining elements from nums2 (while j < n)
  6. Copy the entire temp array back into nums1

Code

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> temp;
        int i = 0, j = 0;
        
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                temp.push_back(nums1[i]);
                i++;
            } else {
                temp.push_back(nums2[j]);
                j++;
            }
        }
        
        while (i < m) {
            temp.push_back(nums1[i]);
            i++;
        }
        
        while (j < n) {
            temp.push_back(nums2[j]);
            j++;
        }
        
        for (int k = 0; k < m + n; k++) {
            nums1[k] = temp[k];
        }
    }
};
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        temp = []
        i, j = 0, 0
        
        while i < m and j < n:
            if nums1[i] <= nums2[j]:
                temp.append(nums1[i])
                i += 1
            else:
                temp.append(nums2[j])
                j += 1
        
        while i < m:
            temp.append(nums1[i])
            i += 1
        
        while j < n:
            temp.append(nums2[j])
            j += 1
        
        for k in range(m + n):
            nums1[k] = temp[k]
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[m + n];
        int i = 0, j = 0, k = 0;
        
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                temp[k++] = nums1[i++];
            } else {
                temp[k++] = nums2[j++];
            }
        }
        
        while (i < m) {
            temp[k++] = nums1[i++];
        }
        
        while (j < n) {
            temp[k++] = nums2[j++];
        }
        
        for (int idx = 0; idx < m + n; idx++) {
            nums1[idx] = temp[idx];
        }
    }
}

Complexity Analysis

Time Complexity: O(m + n)

Each element from nums1 and nums2 is visited exactly once during the merge. The copy-back step also takes O(m + n). Total: O(m + n).

Space Complexity: O(m + n)

We allocate a temporary array of size m + n to hold the merged result before copying it back into nums1. This is the main drawback of this approach.

Why This Approach Is Not Efficient

The two-pointer merge achieves optimal O(m + n) time, which is great. However, it uses O(m + n) extra space for the temporary array. The problem specifically tells us that nums1 already has enough space at the end to accommodate all elements. This is a strong hint that we should be able to merge in-place without any extra array.

The challenge with merging from the front in-place is that writing into nums1[0], nums1[1], ... would overwrite the original nums1 elements before we process them. But what if we fill from the back instead? The trailing zeros in nums1 are just empty space waiting to be used. If we place the largest elements first (at the end of nums1), we never overwrite unprocessed elements.

This insight leads to the optimal three-pointer approach that works backwards.

Optimal Approach - Three Pointers from End

Intuition

The key insight is to fill nums1 from the back rather than the front. We use three pointers:

  • Pointer p1 starts at the last meaningful element of nums1 (index m - 1)
  • Pointer p2 starts at the last element of nums2 (index n - 1)
  • Pointer write starts at the very last position of nums1 (index m + n - 1)

At each step, we compare the elements at p1 and p2, pick the larger one, and place it at the write position. Then we decrement the appropriate pointer.

Why does this work without overwriting? Consider the write pointer at position write and the p1 pointer at position p1. At every step, write ≥ p1 because write starts at m+n-1 and p1 starts at m-1, and they both decrease by at most 1 each step. So we never write into a position that still holds an unprocessed nums1 element.

Think of it like packing boxes into a truck from the back. You have two piles of differently-sized boxes already sorted by size. You pick the largest box from either pile and slide it to the back of the truck first, then the next largest, and so on. The remaining empty space in the truck is always in front of where you last placed a box.

Step-by-Step Explanation

Let's trace through with nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3:

Step 1: Initialize p1 = 2 (last meaningful element of nums1, value 3), p2 = 2 (last element of nums2, value 6), write = 5 (last position of nums1).

Step 2: Compare nums1[p1]=3 vs nums2[p2]=6. 6 ≥ 3, so place 6 at nums1[5]. Decrement p2 to 1, write to 4. nums1 = [1, 2, 3, 0, 0, 6].

Step 3: Compare nums1[p1]=3 vs nums2[p2]=5. 5 ≥ 3, so place 5 at nums1[4]. Decrement p2 to 0, write to 3. nums1 = [1, 2, 3, 0, 5, 6].

Step 4: Compare nums1[p1]=3 vs nums2[p2]=2. 3 ≥ 2, so place 3 at nums1[3]. Decrement p1 to 1, write to 2. nums1 = [1, 2, 3, 3, 5, 6].

Step 5: Compare nums1[p1]=2 vs nums2[p2]=2. 2 ≥ 2, so place nums1's 2 at nums1[2]. Decrement p1 to 0, write to 1. nums1 = [1, 2, 2, 3, 5, 6].

Step 6: Compare nums1[p1]=1 vs nums2[p2]=2. 2 ≥ 1, so place 2 at nums1[1]. Decrement p2 to -1, write to 0. nums1 = [1, 2, 2, 3, 5, 6].

Step 7: p2 < 0, so nums2 is exhausted. The remaining nums1 elements (just 1 at index 0) are already in their correct position. Done! nums1 = [1, 2, 2, 3, 5, 6].

Three Pointers from End — In-Place Merge — Watch how three pointers fill nums1 from the back by always choosing the larger of the two candidates. This avoids overwriting unprocessed elements and needs no extra space.

Algorithm

  1. Initialize three pointers: p1 = m - 1, p2 = n - 1, write = m + n - 1
  2. While both p1 ≥ 0 and p2 ≥ 0:
    • If nums1[p1] ≥ nums2[p2], place nums1[p1] at nums1[write] and decrement p1
    • Otherwise, place nums2[p2] at nums1[write] and decrement p2
    • Decrement write
  3. While p2 ≥ 0 (remaining nums2 elements):
    • Place nums2[p2] at nums1[write]
    • Decrement both p2 and write
  4. No need to handle remaining nums1 elements — they are already in place

Code

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int write = m + n - 1;
        
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] >= nums2[p2]) {
                nums1[write] = nums1[p1];
                p1--;
            } else {
                nums1[write] = nums2[p2];
                p2--;
            }
            write--;
        }
        
        while (p2 >= 0) {
            nums1[write] = nums2[p2];
            p2--;
            write--;
        }
    }
};
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        p1 = m - 1
        p2 = n - 1
        write = m + n - 1
        
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] >= nums2[p2]:
                nums1[write] = nums1[p1]
                p1 -= 1
            else:
                nums1[write] = nums2[p2]
                p2 -= 1
            write -= 1
        
        while p2 >= 0:
            nums1[write] = nums2[p2]
            p2 -= 1
            write -= 1
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int write = m + n - 1;
        
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] >= nums2[p2]) {
                nums1[write] = nums1[p1];
                p1--;
            } else {
                nums1[write] = nums2[p2];
                p2--;
            }
            write--;
        }
        
        while (p2 >= 0) {
            nums1[write] = nums2[p2];
            p2--;
            write--;
        }
    }
}

Complexity Analysis

Time Complexity: O(m + n)

Each of the m + n elements is placed exactly once. Every iteration of the main loop places one element and decrements one pointer, so the loop runs at most m + n times total. The cleanup loop for remaining nums2 elements also contributes at most n iterations. Overall: O(m + n).

Space Complexity: O(1)

We use only three integer variables (p1, p2, write) regardless of input size. The merge is done entirely in-place within the existing nums1 array. No temporary array or additional data structures are needed.

This is the best possible complexity for this problem: we must look at every element at least once (so Ω(m + n) time is required), and the problem demands in-place modification (so O(1) space is ideal).