Merge Two Sorted Arrays

Question

Merge two given sorted integer array A and B into a new sorted integer array.

Example

Input: A = [1,2,3,4], B=[2,4,5,6]
Return: [1,2,2,3,4,4,5,6]

Analysis

Two ways to think about this. Two pointers (one for each) for two input arrays until you reach the end for both of them. Or one pointer for the result array, and keep filling it until it's full. (more do the same distance first then fill in the rest).

Do both methods then compare them.

Easy To Get Bug

public int[] mergeSortedArray(int[] A, int[] B) {
    int[] R = new int[A.length + B.length]; //result
    int x = 0, y = 0;

    while (x + y < R.length) {
        if (y >= B.length || (x < A.length && A[x] <= B[y])) {
            R[x+y] = A[x++];
        } else {
            R[x+y] = B[y++];
        }
    }

    return R;
}

Keep filling then handle the case where n > m or n < m will be easier to write bug free code.

Hard to Get Bug

public int[] mergeSortedArray(int[] A, int[] B) {
    if (A == null || B == null)
        return null;
    int[] results = new int[A.length+B.length];
    // merge A and B until one array is exhausted
    int i = 0, ap = 0, bp = 0;
    while (ap < A.length && bp < B.length) {
        if (A[ap] < B[bp]) {
            results[i++] = A[ap++];
        } else {
            results[i++] = B[bp++];
        }
    }
    // if A has leftover elements
    while (ap < A.length) {
        results[i++] = A[ap++];
    }
    // else if B has leftover elements
    while (bp < B.length) {
        results[i++] = B[bp++];
    }
    return results;
}

Merge Sorted Array (LC.88)

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

nums1 has m elements and nums2 has n elements. Assume nums1 can hold m+n elements.

Example

I: nums1 = [1, 2, 3, empty, empty], nums2 = [4, 5]
O: nums1 = [1, 2, 3, 4, 5]
I: nums1 = [1, 2, 3, 4, 0, 0, 0, 0], nums2 = [2, 4, 5, 6]
O: nums1 = [1, 2, 2, 3, 4, 4, 5, 6] // trace this left to right
I: nums1 = [1, 2, 3, 4, 0, 0, 0, 0], nums2 = [2, 4, 5, 6]
O: nums1 = [1, 2, 2, 3, 4, 4, 5, 6] // trace this right to left

Analysis

So this problem is engineered so we can do it "in-place". The brute force solution will be O(n^2) compare it then shift if necessary. Where to merge? Can we do it in one pass? Maybe we can hold a temp variable? Well check out the solution after no clue for 2 min.

ᶘ ᵒᴥᵒᶅ By default our mind is always telling us to start from left -> right or small -> large. What if we start filling from large -> small? ohhhh

Code

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int tail = n + m - 1;
    int p1 = m - 1, p2 = n - 1;
    while (p1 >= 0 && p2 >= 0) {
        if (nums2[p2] >= nums1[p1]) {
            nums1[tail--] = nums2[p2--];
        } else {
            nums1[tail--] = nums1[p1--];
        }
    }
    // if m is bigger, we don't have to do anything b/c nums1 is sorted
    // if n is bigger
    while (p2 >= 0) {
        nums1[tail--] = nums2[p2--];
    }
}

Recap

I can feel a significant improvement by writing analysis and going through thought process. I am no longer the no-clue-run-code-bug Zed, but the new pseudo-code-test-pass Zed. Congrats on understanding (read carefully and do examples) and figuring out (what paradigm / property to use) a problem. That's only the initial step. You also have to write a easy to follow pseudo code and write clear code then review and test a complex case.