Merge Sorted Array

NeetCode: Merge Sorted Array · LeetCode: 88. Merge Sorted Array · Difficulty: Easy

nums1 has length m + n: its first m elements are sorted values and the last n are zeros reserved for the result. nums2 has n sorted values. Merge nums2 into nums1 so that nums1 is one sorted array.

Example

Text

Input:  nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3    Output: [1, 2, 2, 3, 5, 6]
Input:  nums1 = [0], m = 0, nums2 = [1], n = 1                         Output: [1]

Brute force: copy, then sort

Copy nums2 into the free slots of nums1 and sort the whole thing. Sorting costs O((m + n) log(m + n)) and ignores that both halves are already sorted.

Java

import java.util.Arrays;

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = {1, 2, 3, 0, 0, 0};
        s.merge(a, 3, new int[]{2, 5, 6}, 3);
        System.out.println(Arrays.toString(a));
        int[] b = {0};
        s.merge(b, 0, new int[]{1}, 1);
        System.out.println(Arrays.toString(b));
        int[] c = {1};
        s.merge(c, 1, new int[]{}, 0);
        System.out.println(Arrays.toString(c));
    }
}

Output

[1, 2, 2, 3, 5, 6]
[1]
[1]

Time: O((m + n) log(m + n)). Space: O(log(m + n)) for the sort: Arrays.sort on int[] uses a dual-pivot quicksort, which sorts in place and recurses on the stack.

Optimal: fill from the back

Merging from the front would overwrite values of nums1 that are still unread, but the back of nums1 is free space. Write the largest remaining element there: compare the last unmerged element of each array, put the bigger one at position k, and move that pointer and k left. Position k never holds an unread value, because k is always at least as far right as the unread part of nums1.

If nums1 is exhausted first, the rest of nums2 is copied over. If nums2 is exhausted first, the remaining nums1 elements are already in place, so the loop ends.

i and j hold the number of elements left in each array and are read at index i - 1 and j - 1, so the loop conditions i > 0 and j > 0 double as bounds checks. The method returns nothing: it changes nums1 in place, as LeetCode requires.

Java

import java.util.Arrays;

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = {1, 2, 3, 0, 0, 0};
        s.merge(a, 3, new int[]{2, 5, 6}, 3);
        System.out.println(Arrays.toString(a));
        int[] b = {0};
        s.merge(b, 0, new int[]{1}, 1);
        System.out.println(Arrays.toString(b));
        int[] c = {1};
        s.merge(c, 1, new int[]{}, 0);
        System.out.println(Arrays.toString(c));
    }
}

Output

[1, 2, 2, 3, 5, 6]
[1]
[1]

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