Question

Can it be done without creating a new merged array, meaning sorting using only B and A?

Comments

That was easy if you think out of the box - in reverse :)

---

Yet another solution that merges from the end of A. Maybe this is easier to understand:

{{

class Solution {

public:

void merge(int A[], int m, int B[], int n) {

    // Can be done this way also:
    //   copy( B, B + n, A + m);
    //   sort(A, A + m + n);

    // Merge elements inplace starting from the end of A[]:
    int *write_it = A + m + n - 1;
    int *read_a = A + m - 1;
    int *read_b = B + n - 1;
    while (read_a >= A && read_b >= B) {

        int a = *read_a;
        int b = *read_b;

        if (a > b) {

            (*write_it) = a;
            read_a--;
        }
        else {

            (*write_it) = b;
            read_b--;
        }

        write_it--;
    }

    // If there some extra element in B yet to be moved:        
    if (read_b >= B) {

        copy(B, read_b + 1, A);
    }

}

};

}}

Answer 1

Yes, you are suppose to merge B into A without using any extra space.

Answer 2

yes, you can do this at runtime:

class Solution {
public:
void merge(int A[], int m, int B[], int n) {
    for (int idx = m + n - 1; idx >= 0; idx--) {
        if (m <= 0) {
            A[idx] = B[--n]; 
        } else if (n <= 0) {
            break;
        } else if (A[m-1] < B[n-1]) {
            A[idx] = B[--n];
        } else {
            A[idx] = A[--m];
        }
    }
}
};

Answer 3

Yes, Try solve it by fill proper int to array A's tail first.

Answer 4

of course, you can just copy B into A, from end to the start

if you're familiar with STL, you can refer to the method of rbegin iterator

Answer 5

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {

        auto posA = m - 1;
        auto posB = n - 1;
        auto posWrite =  n + m - 1;

        while (posB >= 0 && posA >= 0) {
            if (B[posB] < A[posA])
                A[posWrite--] = A[posA--];
            else
                A[posWrite--] = B[posB--];
        }

        for (; posB >= 0; --posWrite, --posB)
            A[posWrite] = B[posB];
    }
};

Comments

Answers you've written should describe your code with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.

Answer 6

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

            }
        } 
}