# C++ solution, runtime O(n), in-place, easy to understand

• The idea is to go from the last indexes of both arrays, compare and put elements from either A or B to the final position, which can easily get since we know that A have enough space to store them all and we know size of A and B. Please refer to the comments for details.

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

int a=m-1;
int b=n-1;
int i=m+n-1;    // calculate the index of the last element of the merged array

// go from the back by A and B and compare and put to the A element which is larger
while(a>=0 && b>=0){
if(A[a]>B[b])   A[i--]=A[a--];
else            A[i--]=B[b--];
}

// if B is longer than A just copy the rest of B to A location, otherwise no need to do anything
while(b>=0)         A[i--]=B[b--];
}
};``````

• Why havent you checked the condition if A is longer than B and all the elements in array A are iterated and the only remaining is the elements in B.. in that case shouldnt you add an extra while loop like you did for B

• the situation you described will fall into the second wile loop, because when all the elements in A are iterated, it will get out of the first wile loop, then second loop will be executed.

• jayasuryajeyakodi, to answer your question "Why havent you checked the condition if A is longer than B ", problem description says "You may assume that A has enough space". So from the beginning I know that I need to put all elements in A.

• @JackBauer i have a question:

for A is 1000, 1001, 10002, 1003, 1004, 1005, but for B is 1, 2. I think your solution is wrong for this case.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.