CareerCup

If the input arrays are sorted then we have no problem if not we have two option.
1. merge and short.
2. short and merge.

the second option is better as shorting 2 smaller array takes less time then the bigger one.

are arrays sorted ??
if yes the you can do it in O(2n) time
else O(nlogn) time
space required is O(n)

@all what abhi said is right but if one array is big & have enough space to store 2nd array elements then it can be done in O(nlogn) for unsorted & O(n) for sorted array

& space required O(1)..isn't it...else i don't think any problem in this question if u wish i can post the exact working code this..

I think all forget my orginal question. Merge short is fine but also need to take care duplicate value while merging. Because in two array we have duplicates and merged array should not have any duplicate. Please provide a code snippet if possible.

Hi

Do you think that if we merge as usual (like after merge sort) but on encountering same numbers, increment both pointers (running on the two arrays by 1) ?

That is

// Untested code
Let i run on Sorted Arr 1 and j run on sorted array 2.
i = 0;
j = 0;
Usual Merge routine (with a twist) {
while(i < arr1.length && j < arr2.length) {
 if(arr1[i].compareTo(arr2[j]) < 0)
   copy arr1[i] to arr3[k]
   i++;
 else if(arr[i].compareTo(arr2[j]) > 0)
   copy arr2[j] to arr3[k]
   j++;
 else // when they are equal
   // copy either one
   copy arr1[i] to arr3[k]
   i++;
   j++;
}
k++;
} // end of merge

Think this might work ? Let me know if there are bugs. I m testing it anyway.

Good luck !

Ooops ! the k++ be inside the while loop.

the above pseudocode wont work if duplicates are within the same sub array. In that case,

we can check arr1[i] (or arr2[j] whichever is to be copied) with arr3[k-1] after NULL check.

techpuzzl.wordpress.com/2010/01/22/merge-two-sorted-arrays/

int MergeArrays()
{
//Assume inputs, C is destination but might not get filled till x+y and hence we return how much it is filled
A[x] B[y] C[x+y]

i=j=k=0;

while(i < x && j < y)
{
i = skipDupesWithinArray(A, i, x);
j = skipDupesWithinArray(B, j, y);

if(i == x)
{
return AssignRestArray(B, j, y, C, k);
}

if(j == y)
{
return AssignRestArray(A, i, x, C, k);
}

if(A[i] == B[j])
{
j++;
}
else if(A[i] < B[j])
{
C[k++] = A[i++];
}
else
{
C[k++] = B[j++];
}
}
return k;
}

int skipDupesWithinArray(Array H, int currPos, int maxNum)
{
while(currPos + 1 < maxNum)
{
if(H[currPos] == H[currPos] + 1)
currPos++;
}
return currPos;
}

int AssignRestArray(Array H, int currPos, int maxNum, Array X, int xPos)
{
while(currPos < maxNum)
{
X[xPos++] = H[currPos++];
currPos = skipDupesWithinArray(H, currPos, maxNum);
}
return xPos;
}

first do heap sort of two arrays that is 0(nlgn) time
now just takes a loop seperately in two arrays and remove easily duplicates
now just using the space of third array 0(m+n)
do merge which is really very easy :)

Assuming both arrays are sorted.
a[] is of size M & b[] is of size N.
c is the third array which contains the sorted data avoiding duplicates.

i=0;j=0; top=-1;
while(i<M && j<N)
{
	if(a[i]<b[j])
		c[++top]=a[i++];
	else if(a[i]>b[j])
		c[++top]=b[j++];
	else
	{
		c[++top]=a[i++];
		j++;
	}
}
while(i<M)
	c[++top]=a[i++];
while(j<N)
	c[++top]=b[j++];