Merge Sorted Array [Easy] — Three Pointers From End

Problem Statement

Merge nums2 into nums1 in-place (nums1 has enough space). Both are sorted. m and n are their respective initial sizes.

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

Intuition

Fill from the back: compare nums1[m-1] and nums2[n-1], place the larger at position m+n-1. Move backwards.

Solutions

C

void merge(int* a, int m, int* b, int n) {
    int i=m-1, j=n-1, k=m+n-1;
    while (i>=0&&j>=0) a[k--]=a[i]>b[j]?a[i--]:b[j--];
    while (j>=0) a[k--]=b[j--];
}

C++

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i=m-1, j=n-1, k=m+n-1;
    while (i>=0&&j>=0) nums1[k--]=nums1[i]>nums2[j]?nums1[i--]:nums2[j--];
    while (j>=0) nums1[k--]=nums2[j--];
}

Java

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

JavaScript

var merge = function(nums1, m, nums2, n) {
    let i=m-1, j=n-1, k=m+n-1;
    while (i>=0&&j>=0) nums1[k--]=nums1[i]>nums2[j]?nums1[i--]:nums2[j--];
    while (j>=0) nums1[k--]=nums2[j--];
};

Python

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

Complexity

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