LeetCode 88: Merge Sorted Arrays

In this exercise, we need to take 2 sorted arrays and merge them into one sorted array. The change should be done “in place” and the result stored in the first array.

a. Basics of merging arrays

When 2 arrays nums1 and nums2, are sorted, we merge them by traversing both arrays simultaneously, keeping a pointer i for the next element in nums1 and j for the next element in nums2. At each step, we compare nums1[i] and nums2[j], we add the lowest to our current result and increment the index for the corresponding array. If nums1 is of length m and nums2 of length n, this gives use the following:

int i = 0;
int j = 0;
for (int k = 0; k<n+m; k++) {
    if (nums1[i] < nums2[j]) {
        res[k] = nums1[i];
        i++;
    } else {
        res[k] = nums2[j];
        j++;
    }
}

b. Merging edge cases

Of course, the previous implementation is incorrect (good job if you spotted it) and we need to add border case to make sure that we don’t get index out of bounds exceptions. After updating the code to make this work, this give us a complete merge algorithm:

int i = 0;
int j = 0;
for (int k = 0; k<n+m; k++) {
    if (i>=m) {
        res[k] = nums2[j];
        j++;
    } else if (j >= n || nums1[i] < nums2[j]) {
        res[k] = nums1[i];
        i++;
    } else {
        res[k] = nums2[j];
        j++;
    }
}

c. In place constraint, simple copy