Union of two arrays

Question

Given two arrays

int arr1[n]
int arr2[m]

where n > m

Need to write a union of two arrays into one.

For example, if the input arrays are:

   int arr1[] = {1, 3, 4, 5, 7}
   int arr2[] = {2, 3, 5, 6}

Then program should create new array Union as {1, 2, 3, 4, 5, 6, 7}

Implementation can be in C# or Java.

In order to solve it first of all need to to sort the arrays using Merge Sort and then do the union

I looked in the net but did not find the elegant way . Every code that I looked was full of IF's.

Please advice what is the most quick and elegant way to do it

Answer 1

public static void printUnion(int ar1[],int ar2[]) {
        int m = ar1.length;
        int n = ar2.length;
        int i=0,j=0;

        while(i<m && j<n) {
            if( ar1[i] <ar2[j]) {
                System.out.println(ar1[i]);
                i++;
            }else if(ar1[i] > ar2[j]) {
                System.out.println(ar2[j]);
                j++;
            }else {
                System.out.println(ar1[i]);
                i++;
                j++;
            }
        }
        while(i < m)
               System.out.println(ar1[i++]);
        while(j < n)
               System.out.println(ar2[j++]);
}

Same code will work for intersection with minimal changes....

Answer 2

this method should work fairly well, and it will decide which array is bigger so there doesn't need to necessarily be a defined order.

Java:

public static <T> T[] combine(T[] a1, T[] a2)
{
    return combine(a1, a2, a1.length + a2.length);
}
public static <T> T[] combine(T[] a1, T[] a2, int maxlength)
{
    T[] front = null;
    T[] back = null;
    if(a1.length >= a2.length)
    {
        front = a1;
        back = a2;
    }
    else
    {
        front = a2;
        back = a1;
    }
    int len = front.length + back.length;
    if(len > maxlength)
    {
        len = maxlength;
    }
    int n = 0;
    T[] result = Arrays.copyOf(front, len);
    int c = 0;
    for(int i = 0;i < front.length;i++)
    {
        if(i < front.length && c < result.length)
        {
            result[c] = front[i];
            c++;
        }
        if(i < back.length && c < result.length)
        {
            result[c] = back[i];
            c++;
        }
    }
    return result;
}

this is obviously not the most efficient method, but it does completely work. It also includes a capping, if you want to merge them, but only get the first, let's way 5 items, then you can add a parameter of 5 to the method.

You can actually get rid of a lot of waste, there's a lot of messy stuff in here, I'm away from my IDE so it's off my head, I may have stuff that's not needed.

Answer 3

If its an elegant MergeSort you are looking then nothing is more elegant than a recursive function :-)

Here it is :

This is a divide and conquer strategy. We basically divide the array into smaller arrays , sort the smaller arrays and merge them back.

public static void mergesort(int a[],int left, int right){
    /*
    *  Time : O(n log n)
    *  Space : O(n)
    */
    int b[] = new int[right -left+1];
    domergesort(a,left,right,b);
}

public static void domergesort(int a[],int left,int right, int b[]){

    if(left < right){
        int mid = (left+right)/2;
        domergesort(a,left,mid,b);
        domergesort(a,mid+1,right,b);
        merge(a,left,mid,a,mid+1,right,b);
        for(int k=left;k<=right;k++)
            a[k] = b[k-left];
    }
}

Not many ifs too ..

Source : My Blog (http://cloudingitup.blogspot.com/p/reading-guide-arrays.html)

To merge them together as a Union :

public static void merge( int a[], int al, int ar, int b[], int bl, int br, int c[]){
    // al : a's left index ar : a's right index c: merged array
    int i= al;
    int j = bl;
    int k=0;
    int prev = c[0]; 

    while ( i<= ar && j <= br){
        if (a[i] <= b[j])
          if (prev != a[i]) // Too keep the union distinct
              c[k++] = a[i++];
          else
             i++;
        else
            if (prev != b[j]) // Too keep the union distinct
                c[k++] = b[j++];
            else
                j++;

        prev = c[k-1];

    }

    while (i <= ar)
     {
     if (prev != a[i])
        c[k++] = a[i++];
      else
         i++;

       prev = c[k-1];
      }


    while (j <= br)
     {
     if (prev != b[j])
        c[k++] = b[j++];
      else
         j++;
       prev = c[k-1];
      }

}

A driver code to illustrate the code :

int arr1[] = {1,1, 3, 4,4,4,5, 7};
int arr2[] = {2, 3, 5, 6,6,8};
int c[] = new int[8];

merge(arr1,0,7,arr2,0,5,c);

for(int i=0;i<8;i++)
System.out.print(c[i]);

Output: 12345678

Answer 4

In interviews, they usually want to see you solve the problem, rather than using library calls (e.g. arr1.union(arr2) probably wouldn't cut it.)

This is off the top of my head, but something like this should work, and I think is O(n^2). It assumes both arrays are sorted.

union.rb

arr1 = [0,2,4,9,11,12,13]
arr2 = [3,4,7,9,10,11]

def union(n, m)
  if n.last > m.last
    arr1 = n; arr2 = m
  else
    arr1 = m; arr2 = n
  end

  union_array = []
  j = 0
  arr1.each do |x|
    while j < arr2.length && arr2[j] < x
      if arr2[j] < x
        union_array << arr2[j] unless arr2[j] == union_array.last
        j += 1
      end
    end
    union_array << x
  end
  union_array
end

puts union(arr1, arr2)

Answer 5

You are correct that merging the two lists as is done in Merge Sort is the most efficient thing to do. This assumes that the two lists are already sorted, as in your example. Here is an example of how to implement merge:

function merge(left,right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) ≤ first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result

From here, simply do not include repeats in the final output.