Merged integer sorted arrays

One of classic problem using binary search approach.

Problem

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Solution

The key to solve this problem is moving element of A and B backwards. If B has some elements left after A is done, also need to handle that case. The takeaway message from this problem is that the loop condition.

Solution 1

In this case We have two arrays A and B, but array A have m elements to merge, and m+n placeholders for all elements.

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
 
        while(m > 0 && n > 0){
            if(A[m-1] > B[n-1]){
                A[m+n-1] = A[m-1];
                m--;
            }else{
                A[m+n-1] = B[n-1];
                n--;
            }
        }
 
        while(n > 0){
            A[m+n-1] = B[n-1];
            n--;
        }
    }
}

Memory O(0) (uses only arrays what we have), Steps: O(m+n) - linear

Solution 2

public void merge(int A[], int m, int B[], int n) {
	int i = m - 1;
	int j = n - 1;
	int k = m + n - 1;
 
	while (k >= 0) {
		if (j < 0 || (i >= 0 && A[i] > B[j]))
			A[k--] = A[i--];
		else
			A[k--] = B[j--];
	}
}

Memory O(3); Steps: O(m+n)