LeetCode: Merge Sorted Array

leetcode Merge Sorted Array Problem Description:

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

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

leetcode Merge Sorted Array  Solution and Source Code:

Test your ability to think out of box. Just a very little change of the regular merge sort. For this problem, we start from the largest number in the two sorted arrays and put the larger one into the tail of array A. Essentially, this is the same as regular merger sort. The following is the accepted source code:

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

leetcode Merge Sorted Array  Tips and Remarks:

If you stuck at some point thinking about the tricky solution, then a better option would be start over and try to think out of box (e.g., reverse way). Usually, the solution is not as complex as you think, it is often very simple with short and elegant code.

Written on April 27, 2013