88. Merge Sorted Array

Intuition

We need to merge two sorted arrays nums1 and nums2 into nums1 and keep it sorted.

Approach

1. Copy elements of nums2 into nums1 starting from index m.
2. Sort the merged array nums1 using appropriate sorting functions.

Complexity

• Time complexity: O((m+n) * log(m+n)) where m is the number of elements in nums1, and n is the number of elements in nums2.
• Space complexity: O(1) because we are using constant extra space.

Code

C

int compare(const void* a, const void* b);

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    for (int i = m, j = 0; j < n; ++i, ++j) {
        nums1[i] = nums2[j];
    }
    qsort(nums1, nums1Size, sizeof(int), compare);
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

C++

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        for (int i = m, j = 0; j < n; ++i, ++j) {
            nums1[i] = nums2[j];
        }
        sort(nums1.begin(), nums1.begin() + m + n);
    }
};

Python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        for i in range(m, m + n):
            nums1[i] = nums2[i - m]
        nums1[:m + n] = sorted(nums1[:m + n])

Java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m, j = 0; j < n; ++i, ++j) {
            nums1[i] = nums2[j];
        }
        Arrays.sort(nums1, 0, m + n);
    }
}

JavaScript

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
  for (var i = m, j = 0; j < n; i++, j++) {
    nums1[i] = nums2[j];
  }
  nums1.sort((a, b) => a - b);
};

TypeScript

/**
 Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  for (let i = m, j = 0; j < n; i++, j++) {
    nums1[i] = nums2[j];
  }
  nums1.sort((a, b) => a - b);
}

Go

func merge(nums1 []int, m int, nums2 []int, n int) {
    for i, j := m, 0; j < n; i, j = i+1, j+1 {
        nums1[i] = nums2[j]
    }
    sort.Ints(nums1[:m+n])
}

C#

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m, j = 0; j < n; ++i, ++j) {
            nums1[i] = nums2[j];
        }
        Array.Sort(nums1, 0, m + n);
    }
}