Merge Sorted Array - Leetcode Solution

The Merge Sorted Array problem on LeetCode asks for a solution to merge two sorted integer arrays into one sorted array. The two input arrays are already sorted in non-descending order, and one of the arrays has enough space at the end to hold all the elements of the two arrays.

Here's a detailed solution to the problem:

void merge(vector<int>& nums1, int m, vector<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--];
        }
    }
}

Explanation:

We start by initializing three pointers i, j, and k. i and j point to the last elements of nums1 and nums2, respectively. k points to the last position of the merged array, which is m + n - 1.

We then iterate through the arrays in reverse order using a while loop. We compare the values at i and j and use the greater one to fill the kth position in nums1. We decrement k, i, or j based on which value we chose. We continue this process until either we reach the beginning of nums2 (j < 0) or we have filled all positions in nums1 (k < 0).

This algorithm has a time complexity of O(m+n) and a space complexity of O(1), since we are only modifying the existing arrays, and not creating any new data structures.

1