Merge Sorted Array

Easy Problem 7 of 151 Java and Python

Problem

You are given two sorted integer arrays nums1 and nums2, and two integers m and n: the number of real elements in each.

nums1 has length m + n; its last n slots are zeros that make room for nums2. Merge nums2 into nums1 so that nums1 ends up sorted. Do not return anything.

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]

Example 2

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Why: nums1 has no real elements, so the result is nums2.

Constraints

nums1.length == m + n, nums2.length == n
0 ≤ m, n ≤ 200
-10⁹ ≤ nums1[i], nums2[j] ≤ 10⁹

Explanation

Merging from the front would overwrite numbers in nums1 that you still need. The empty space is at the back, so fill from the back: the largest remaining element of either array goes into the last free slot.

Approach 1 · Naive

Append and sort

Time O((m + n) log(m + n))
Space O(1) extra

Copy nums2 into the empty slots and sort the whole array. Correct, but it ignores that both inputs are already sorted.

Copy nums2[i] into nums1[m + i].
Sort nums1.

Java

import java.util.*;

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);
    }
}

Python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[m:] = nums2
        nums1.sort()

Approach 2 · Optimal

Three pointers from the end

Time O(m + n)
Space O(1)

Point i at the last real element of nums1, j at the last element of nums2, and k at the last slot. Place the larger of nums1[i] and nums2[j] at k.

Set i = m - 1, j = n - 1, k = m + n - 1.
While j >= 0: if i >= 0 and nums1[i] > nums2[j], put nums1[i] at k and move i; otherwise put nums2[j] at k and move j. Move k each time.
Anything left in nums1 is already in place.

Java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

Python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j, k = m - 1, n - 1, m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

Complexity compared

Approach	Time	Space
Naive Append and sort	O((m + n) log(m + n))	O(1) extra
Optimal Three pointers from the end	O(m + n)	O(1)

Key takeaways

When the free space is at the end of an array, fill it from the end.
The loop only needs to run while nums2 has elements left.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem