CareerCup

1. collapse all the spaces in the first array starting from the end (two indices needed to keep track of start and end of the continuous free space) - takes O(n) time.
2. merge two arrays - takes O(n) time.

It did not say if sorted result is required. If yes, it is a variation to question 9626448.

what does space mean here? in the middle or end ??? can u explain in detail

Its better to fill the spaces of array A with elements of array B, then sort them. It takes O(n)+O(nlgn) time, so effectively O(nlgn).

<pre lang="" line="1" title="CodeMonkey21388" class="run-this"> public class MergeAandB
{
public int[] Merge(int[] A, int[] B)
{
//Arrange all place holders at the end
int indxStartPh = 0, indxEndPh = 0;
for (; A[indxStartPh] != -1; indxStartPh++) ;
indxEndPh = indxStartPh;
for (; A[indxEndPh] == -1 && indxEndPh < A.Length; indxEndPh++) ;
while (indxEndPh < A.Length-1)
{
if (A[indxEndPh+1] != -1)
{
//swap with indx start place-holder
A[indxStartPh++] = A[indxEndPh + 1];
A[indxEndPh++ + 1] = -1;
}
//find the end of current place holders block
else
{
for (; A[indxEndPh] == -1 && indxEndPh < A.Length; indxEndPh++) ;
}
}

//merge arrays: A and B
int indexA = indxStartPh - 1;
int indexB = B.Length - 1;
int sortIndex = A.Length - 1;
while (indexB>=0 && indexA>=0)
{
//merge A
if (A[indexA] >= B[indexB])
{
A[sortIndex--] = A[indexA];
A[indexA--] = -1;
}
//merge B
else
{
A[sortIndex--] = B[indexB--];
}
}

while (indexB >= 0)
{
A[sortIndex--] = B[indexB--];
}

return A;
}
}</pre><pre title="CodeMonkey21388" input="yes">
</pre>

Here is the most efficient VBA code with test arrays


-----------
Sub Arr2()

Dim l1, l2, l3 As Integer

l1 = 4 'sorted 1
l2 = 3 'sorted 2
l3 = l1 + l2 '

Dim aR1(4) As Integer
Dim aR2(7) As Integer

aR1(0) = -32768
aR1(1) = -3
aR1(2) = 7
aR1(3) = 9


aR2(0) = -2
aR2(1) = 7
aR2(2) = 16



'Compare the largest sorted elemets of arrays and move the largest to the last empty space
'So
'l1 is position of current largest element of array 1
'l2 is position of current largest element of array 2
'l3 is position of empty space for the next largest element


Do While l1 > 0 And l2 > 0
If aR1(l1 - 1) > aR2(l2 - 1) Then
aR2(l3 - 1) = aR1(l1 - 1)
'Move to the next largest position
l1 = l1 - 1
Else
aR2(l3 - 1) = aR2(l2 - 1)
'Move to the next largest position
l2 = l2 - 1
End If
'Move Empty space for the next largest element
l3 = l2 + l1 'same as l3 = l3 - 1
Loop


'If all elements fro Array 1 checked and processed(i.e l1 = 0) we are done
'But if Array 1 has some elements left we need just to move them to beginning of array2 one by one
'Array2 has empty spaces ready for them!!!

Dim i As Integer
For i = 0 To l1 - 1
aR2(i) = aR1(i)
Next
For i = 0 To 6
Debug.Print aR2(i)
Next

'Clean array1 if you wish
ReDim aR2(4)

Exit Sub