CareerCup

I probably would have merged them all into a new array. Just have 3 indexes pointing to the start of each array. Take the smallest value referenced by the indexes, append to the new array, and then increment that index. Do this until each index equals the len of it's corresponding array. Return the newly created array.

If you follow the assumptions you made where there is enough room in array1, then you can use a similar algorithm except go from the end of the arrays.

i1 = end of array1 (last number in array, not the size of array)
i2 = end of array2
i3 = end of array3
insertIndex = len(array1) - 1

while (i1, i2, i3 >= 0)
    if i1 largest
	  a1[insertIndex--] = array1[i1--]
    else if i2 largest
          a1[insertIndex--] = array2[i2--]
    else if i3 largest
          a1[insertIndex--] = array3[i3--]

That's the basics of it, there are boundary cases you have to check like when the indexes reach -1.

if there is a better or faster way to do this with all three arrays at the same time (instead of merging two at a time and then use that result with the third array), please advise. I'm very much interested to learn.

This was my code. There were some syntax errors which I corrected in this code:

public static int[] ThreeMergeSortedArrays(int[] a, int[] b, int[] c)
       {
           int[] res = TwoMergeSortedArrays(a, b);
           res = TwoMergeSortedArrays(res, c);
           return res;
       }


       public static int[] TwoMergeSortedArrays(int[] a1, int[] a2)
       {
           //this is under the assumption that array a1 has space to fit in entire array a2. No error conditions have been checked.
           int i;
           int m = a2.Length - 1;
           int n = a1.Length - 1 - a2.Length;
           if (a2[0] > a1[n])
           {
               for (i = 0; i < a2.Length; i++)
                   a1[i + 1 + n] = a2[i];
               return a1;
           }
           for (int k = 0; m >= 0 && n >= 0; k++)
           {
               if (a1[n] > a2[m])
               {
                   a1[a1.Length - 1 - k] = a1[n];
                   n--;
               }
               else
               {
                   a1[a1.Length - 1 - k] = a2[m];
                   m--;
               }
           }
           if (n < 0 && m >= 0)
           {
               while (m >= 0)
               {
                   a1[m] = a2[m];
                   m--;
               }
           }
           return a1;

}

Create an array equal to the length of the three arrays.
Fill the array from the last. Since the array is already sorted, starting to fill from the last will help.

what are the other question in the test??

Was the merged array supposed to maintain all values in sorted order?

public static void main(String[] args) {
int a[] = {0,3,6,9,12,15};
int b[] = {2,4,6,8,10};
int c[] = {1,2,3,4,5,6};
//Create a new array that is supposed to hold the final output of sorted values across the 3 arrays.
int d[] = new int[a.length+b.length+c.length];

//Copy the first array as it is (this can be any array)
for (int i=0;i<a.length;i++) {
d[i] = a[i];
}
//For the remaining two arrays, add element from each of the two arrays into the final array via insertion sort.
merge(b,d,a.length);
merge(c,d,a.length+b.length);

for (int i=0;i<d.length;i++) {
System.out.print(d[i]+" ");
}

}

//Adds the elements from fromArray into the final toArray via insertion sort.
public static void merge(int fromArray[], int toArray[], int currentIndex) {
int val = 0;
for (int i=0;i<fromArray.length;i++) {
val = fromArray[i];
int j = currentIndex;
while (j > 0 && toArray[j-1] > val) {
toArray[j] = toArray[j-1];
j--;
}
toArray[j] = val;
currentIndex++;
}
}

public static void main(String[] args) {
int a[] = {0,3,6,9,12,15};
int b[] = {2,4,6,8,10};
int c[] = {1,2,3,4,5,6};
//Create a new array that is supposed to hold the final output of sorted values across the 3 arrays.
int d[] = new int[a.length+b.length+c.length];
//Copy the first array as it is (this can be any array)
for (int i=0;i<a.length;i++) {
d[i] = a[i];
}
//For the remaining two arrays, add element from each of the two arrays into the final array via insertion sort.
merge(b,d,a.length);
merge(c,d,a.length+b.length);
for (int i=0;i<d.length;i++) {
System.out.print(d[i]+" ");
}
}
//Adds the elements from fromArray into the final toArray via insertion sort.
public static void merge(int fromArray[], int toArray[], int currentIndex) {
int val = 0;
for (int i=0;i<fromArray.length;i++) {
val = fromArray[i];
int j = currentIndex;
while (j > 0 && toArray[j-1] > val) {
toArray[j] = toArray[j-1];
j--;
}
toArray[j] = val;
currentIndex++;
}
}

public static void main(String[] args) {
int a[] = {0,3,6,9,12,15};
int b[] = {2,4,6,8,10};
int c[] = {1,2,3,4,5,6};
//Create a new array that is supposed to hold the final output of sorted values across the 3 arrays.
int d[] = new int[a.length+b.length+c.length];
//Copy the first array as it is (this can be any array)
for (int i=0;i<a.length;i++) {
d[i] = a[i];
}
//For the remaining two arrays, add element from each of the two arrays into the final array via insertion sort.
merge(b,d,a.length);
merge(c,d,a.length+b.length);
for (int i=0;i<d.length;i++) {
System.out.print(d[i]+" ");
}
}
//Adds the elements from fromArray into the final toArray via insertion sort.
public static void merge(int fromArray[], int toArray[], int currentIndex) {
int val = 0;
for (int i=0;i<fromArray.length;i++) {
val = fromArray[i];
int j = currentIndex;
while (j > 0 && toArray[j-1] > val) {
toArray[j] = toArray[j-1];
j--;
}
toArray[j] = val;
currentIndex++;
}
}

public static void main(String[] args) {
int a[] = {0,3,6,9,12,15};
int b[] = {2,4,6,8,10};
int c[] = {1,2,3,4,5,6};
//Create a new array that is supposed to hold the final output of sorted values across the 3 arrays.
int d[] = new int[a.length+b.length+c.length];
//Copy the first array as it is (this can be any array)
for (int i=0;i<a.length;i++) {
d[i] = a[i];
}
//For the remaining two arrays, add element from each of the two arrays into the final array via insertion sort.
merge(b,d,a.length);
merge(c,d,a.length+b.length);
for (int i=0;i<d.length;i++) {
System.out.print(d[i]+" ");
}
}
//Adds the elements from fromArray into the final toArray via insertion sort.
public static void merge(int fromArray[], int toArray[], int currentIndex) {
int val = 0;
for (int i=0;i<fromArray.length;i++) {
val = fromArray[i];
int j = currentIndex;
while (j > 0 && toArray[j-1] > val) {
toArray[j] = toArray[j-1];
j--;
}
toArray[j] = val;
currentIndex++;
}
}

public static int[] merge2(int[] a1, int[] a2){
		int[] mergedArr = new int[(a1.length + a2.length)];
		int i1 = 0, i2 = 0, t = 0;
		int tota = a1.length + a2.length;
		while(t < tota){
			if (i1 == a1.length){
				while(i2 < a2.length){
					mergedArr[t++] = a2[i2++];
				}
				break;
			}
			else if (i2 == a2.length){
				while(i1 < a1.length){
					mergedArr[t++] = a1[i1++];
				}
				break;
			}
			else if (a1[i1] < a2[i2]){
				mergedArr[t++] = a1[i1++];		
			}
			else {
				mergedArr[t++] = a2[i2++];
			}
		}	
		return mergedArr;
	}
	
	public static int[] merge3 (int[] a1, int[] a2, int[] a3){
		int[] mergedArr = new int[(a1.length + a2.length + a3.length)];
		
		int temp1[] = merge2(a1,a2);
		mergedArr = merge2(temp1,a3);
		
		return mergedArr;
	}

std::vector<int> Merge3(std::vector<int>& v1, std::vector<int>& v2, std::vector<int>& v3) 
{
   std::vector<int> rval;
   std::vector<int>::iterator i1 = v1.begin(), i2 = v2.begin(), i3 = v3.begin(); 

   while ((i1 != v1.end()) || (i2 != v2.end()) || (i3 != v3.end()))
   {
      std::vector<int>::iterator* lowest = NULL;
      if (i1 != v1.end())
         lowest = &i1;
      if (i2 != v2.end())
         lowest = lowest ? (*i2 < **lowest ? &i2 : lowest) : &i2;
      if (i3 != v3.end())
         lowest = lowest ? (*i3 < **lowest ? &i3 : lowest) : &i3;
      rval.push_back(*(*lowest)++);
   }
   
   return rval;
}

Based on suggestions from alregith and adam - here is the code to process three sorted arrays from the end:

public int[] ThreeMergeSortedArrays(int[] a1, int[] a2, int[] a3)
        {
            int a1L = a1.Length-1,
                a2L = a2.Length-1,
                a3L = a3.Length-1;
                
            int[] result = new int[a1.Length + a2.Length + a3.Length];
            int resL = result.Length-1;

            while (a1L >= 0 && a2L >= 0 && a3L >= 0)
            {
                if (a1[a1L] >= a2[a2L] && a1[a1L] >= a3[a3L])
                  result[resL--] = a1[a1L--];
                
                else if (a2[a2L] >= a1[a1L] && a2[a2L] >= a3[a3L])
                  result[resL--] = a2[a2L--];
                
                else
                  result[resL--] = a3[a3L--];
            }

                if (a1L < 0)
                {
                    while (a2L >= 0 && a3L >= 0)
                    {
                        if (a2[a2L] >= a3[a3L])
                          result[resL--] = a2[a2L--];
                        else
                          result[resL--] = a3[a3L--];
                    }
                    if (a2L < 0)
                        result[resL] = a3[a3L];
                    else
                        result[resL] = a2[a2L];
                }
                else if (a2L < 0)
                {
                    while (a1L >= 0 && a3L >= 0)
                    {
                        if (a1[a1L] >= a3[a3L])
                          result[resL--] = a1[a1L--];
                        else
                          result[resL--] = a3[a3L--];
                    }
                    if (a1L < 0)
                        result[resL] = a3[a3L];
                    else
                        result[resL] = a1[a1L];
                }
                else
                {
                    while (a1L >= 0 && a2L >= 0)
                    {
                        if (a1[a1L] >= a2[a2L])
                           result[resL--] = a1[a1L--];
                        else
                           result[resL--] = a2[a2L--];
                    }
                    if (a1L < 0)
                      result[resL] = a2[a2L];
                    else
                      result[resL] = a1[a1L];
                }    
             return result;

}

Hello,

Is think that approach to this problem should not be as complex as it sounds.

Generally, I see this problem is a matter of inserting all values from all arrays in Binary Search Tree and performing in-order traversal to add all items in newly allocated array.

Time complexity for this is N log N (to fill binary search tree) and N operations to traverse tree, thus making it O(N log N) operation.

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;


void Merge(vector<int> &v1, vector<int> &v2, vector<int> &v3, vector<int> &output) {
	
	int tsize = v1.size() + v2.size() + v3.size();
	output.resize(tsize);
	
	vector<int> indices;
	indices.push_back(v1.size() - 1);
	indices.push_back(v2.size() - 1);
	indices.push_back(v3.size() - 1);
	
	int oi = tsize - 1;
	while(indices[0] >= 0 || indices[1] >= 0 || indices[2] >= 0) {
		int mx = -1;
		int i = -1;
		if(indices[0] >= 0) {
			i = 0;
			mx = v1[indices[i]];
		}
		if((indices[1] >= 0) && (mx < v2[indices[1]])) {
			i = 1;
			mx = v2[indices[i]];
		}
		if((indices[2] >= 0) && (mx < v3[indices[2]])) {
			i = 2;
			mx = v3[indices[i]];
		}
		output[oi--] = mx;
		//cout << "mx = " << mx << endl;
		indices[i]--;
	}
	
}

int main() {
	vector<int> v1 = {3, 6, 9, 10, 14, 16, 18, 29};
	vector<int> v2 = {1, 5, 7, 11, 14, 19, 23};
	vector<int> v3 = {2, 3, 4, 5};
	vector<int> output;
	Merge(v1, v2, v3, output);
	for(auto i : output)
		cout << i <<  " ";
	return 0;
}

Were they just expecting a 2 dimensional array?

int[][] newArray = {arr1, arr2, arr3};
return newArray;

static int[] MergeArrays(int[] array1, int[] array2)
        {
            int NewLength = array1.Length + array2.Length;
            int[] result = new int[NewLength];

            int last2 = 0;
            for (int i = 0; i < array1.Length; i++)
            {
                for (int j = last2; j < array2.Length; j++)
                {
                    if (array1[i] > array2[j])
                    {
                        result[last2 + i] = array2[j];
                        last2++;
                    }
                    else
                    {
                        result[last2 + i] = array1[i];
                        break;
                    }
                }
                if (last2 == array2.Length) result[i + last2] = array1[i];
            }

            for (int j = last2; j < array2.Length; j++)
            {
                result[j+array1.Length] = array2[j];
            }

            return result;
        }
        static void OutPutArray(int[] array)
        {
            System.Console.WriteLine("");
            for (int i=0; i < array.Length;i++)
            {
                System.Console.Write(array[i]+",");
            }
        }
        static void Main(string[] args)
        {
            int[] array1 = {1,5,7,9};
            int[] array2 = {3,6,10,17,25};
            int[] array3 = { 8, 13, 15, 20 };
            int[] result;

            OutPutArray(array1);
            OutPutArray(array2);
            OutPutArray(array3);
            result = MergeArrays(array1,array2);
            OutPutArray(result);
            result = MergeArrays(result, array3);
            OutPutArray(result);
            System.Console.ReadLine();
        }

public int[] MergedArray(int[] a1, int[] a2, int[] a3)
        {
            LinkedListNode newNode = null;
            LinkedListNode current = null;

            for (int i = 0; i < a1.Length; i++)
            {

                newNode = new LinkedListNode();
                newNode.data = a1[i];

                if (root == null)
                {
                    root = newNode;
                    current = root;
                }
                else
                {
                    current.next = newNode;
                    current = current.next;
                }
            }

            root = MergeLinkedList(root, a2);
            root = MergeLinkedList(root, a3);

            List<int> result = new List<int>();

            while (root != null)
            {
                result.Add(root.data);
                root = root.next;
            }

            root = null;

            return result.ToArray();
        }

        public LinkedListNode MergeLinkedList(LinkedListNode root, int[] array)
        {
            LinkedListNode newNode = null;
            int count = 0;
            LinkedListNode current = root;

            while (root != null && count < array.Length)
            {
                newNode = new LinkedListNode();
                newNode.data = array[count];

                if (root.next == null)
                {
                    root.next = newNode;
                    count += 1;

                }
                else if (root.data < newNode.data && root.next.data > newNode.data)
                {
                    newNode.next = root.next;
                    root.next = newNode;
                    count += 1;
                }


                root = root.next;
            }

            root = current;
           

            return root;

}

C++ implementation: create a third array iterate over each array and add the smallest element to the new array till the arrays are empty.

#include<iostream>
using namespace std;

class Merge{
public:
	void mergeArrays(int *a, int *b, int *c, int as, int bs, int cs, int *final){
		int k=0;
		int j=0;
		int l=0;
		for (int i=0; i<(as+bs+cs); i++){
			if(j<as && k<bs && l<cs){
				if(a[j]<=b[k] && a[j]<=c[l]){
					final[i] = a[j];
					j++;
				}
				else if(b[k]<=a[j] && b[k]<=c[l]){
					final[i] = b[k];
					k++;
				}
				else if(c[l]<=a[j] && c[l]<=b[k]){
					final[i] = c[l];
					l++;
				}
			}
			else if(j<as && k<bs){
				if(a[j]<=b[k]){
					final[i] = a[j];
					j++;
				}
				else {
					final[i] = b[k];
					k++;
				}
			}
			else if(j<as && l<cs){
				if(a[j]<=c[l]){
					final[i] = a[j];
					j++;
				}
				else {
					final[i] = c[l];
					l++;
				}
			}
			else if(k<bs && l<cs){
				if(b[k]<=c[l]){
					final[i] = b[k];
					k++;
				}
				else {
					final[i] = c[l];
					l++;
				}
			}
			else if(j<as){
				final[i] = a[j];
				j++;
			}
			else if(k<bs){
				final[i] = b[k];
				k++;
			}
			else if(l<cs){
				final[i] = c[l];
				l++;
			}
		}
	}
};
int main(){
	int a[] = {1,5,8};
	int b[] = {2,6,7};
	int c[] = {0,8,9,10};
	int final[10];
	int *ptra = a;
	int *ptrb = b;
	int *ptrc = c;
	int *ptr = final;

	Merge *merge = new Merge();
	merge->mergeArrays(ptra,ptrb,ptrc,3,3,4,ptr);
	for(int i=0;i<10;i++)
		cout<<ptr[i];
	cout<<endl;
	system("pause");
}

O(n) solution in C:

#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
int* d;
void merge_arr(int a[],int b[],int c[],int a_size,int b_size,int c_size) {
int small=INT_MAX;
int i,j,k,l;
i=j=k=l=0;
int* p=d;
while(l<a_size+b_size+c_size) {
        small=INT_MAX;
        if(i!=a_size && a[i]<small)
                small=a[i];
        if(j!=b_size && b[j]<small)
                small=b[j];
        if(k!=c_size && c[k]<small)
                small=c[k];
if(small==a[i]) i++;
if(small==b[j]) j++;
if(small==c[k]) k++;
        d[l++]=small;
}
}
int main() {
int a[]={50,51,52};
int b[]={23,43,76,81};
int c[]={31,55};
int i;
int a_size=sizeof(a)/sizeof(a[0]);
int b_size=sizeof(b)/sizeof(b[0]);
int c_size=sizeof(c)/sizeof(c[0]);
d=(int*)malloc(a_size+b_size+c_size);
merge_arr(a,b,c,a_size,b_size,c_size);
for(i=0;i<(a_size+b_size+c_size);i++)
  printf("%d\n",d[i]);
}

O(n) solution in C:

#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
int* d;
void merge_arr(int a[],int b[],int c[],int a_size,int b_size,int c_size) {
int small=INT_MAX;
int i,j,k,l;
i=j=k=l=0;
int* p=d;
while(l<a_size+b_size+c_size) {
        small=INT_MAX;
        if(i!=a_size && a[i]<small)
                small=a[i];
        if(j!=b_size && b[j]<small)
                small=b[j];
        if(k!=c_size && c[k]<small)
                small=c[k];
if(small==a[i]) i++;
if(small==b[j]) j++;
if(small==c[k]) k++;
        d[l++]=small;
}
}
int main() {
int a[]={50,51,52};
int b[]={23,43,76,81};
int c[]={31,55};
int i;
int a_size=sizeof(a)/sizeof(a[0]);
int b_size=sizeof(b)/sizeof(b[0]);
int c_size=sizeof(c)/sizeof(c[0]);
d=(int*)malloc(a_size+b_size+c_size);
merge_arr(a,b,c,a_size,b_size,c_size);
for(i=0;i<(a_size+b_size+c_size);i++)
  printf("%d\n",d[i]);
}