Union of Two Arrays

Internship at OpenGenus

Get this book -> Problems on Array: For Interviews and Competitive Programming

If you want to further your knowledge in data structures and algorithms, or you just started to get ready for Placement preparation. Then you should solve this type of question as basic building blocks.

The Union operation combines the results of two or more queries into a distinct single result set that includes all the rows that belong to all queries in the Union. In this operation, It combines two more queries and removes the duplicates.

So let's clear our purpose.

Objective :
Here,we will look at the Different approaches to find the Union of two arrays.

Key point have to remember

  • The result of the Union must be in sorted order and does not contain any duplicate elements.
  • As a good programmer, you need to find an approach so that your algorithm has time complexity O(m+n), where m and n is the lengths of the two arrays.

There are many ways to reach a solution. Here, we will try to look at some optimal solutions using different data structures.

Different Approaches:


There are many ways that we can follow to solve a problem. But, we have to find out which is the best approach to solve the particular Problem. As we said before, the best solution to this problem has time complexity O(m+n).
Here we will discuss three approaches, which will cover almost all approaches.

For both Unsorted and sorted arrays:
i) Using Set
ii) Using Map
iii) Using searching and sorting (Binary Search)

For Sorted Array:
i) Simple approach using array

Using Set

The result of the Union must be in sorted order and does not contain any duplicate elements. We will move forward with this in mind.

Prerequisite:
1. C++ set.
2. Java TreeSet

Algorithm:

Step 1: Start
Step 2: Declare and Initialize two array objects.
Step 3: Create an empty set.
Step 4: Store the array lengths in two different variables.(In the case of Python and Java 4th step is not necessary.)
Step 5: Insert the first array elements into set object.
Step 6: Insert the second array elements into the set object.
Step 7: Print the elements of the set.

C++:


// C++ program for the union of two arrays using Set

#include <bits/stdc++.h>
using namespace std;

// Driver Code
int main()
{   
    //Declare and Initialize two array objects.
	int a[9] = {18,17,13,12,14,11,11,10,12};
	int b[10] = {16,13,14,13,15,11,12,10,19,10 };
    
    //Create an empty set.
    set<int> s;
    
    // Insert the first array elements into set object.
	for (int i = 0; i < n; i++)
	  s.insert(a[i]);
      
    // Insert the second array elements into the set object.
    for (int i = 0; i < m; i++)
		s.insert(b[i]);
     
     // Print some message if you want to print it.
   cout << "Number of elements after union operation: " << s.size() << endl;
   cout << "The union set of both arrays is :" << endl;
   
   // Print the elements of the set.
   for (auto itr = s.begin(); itr != s.end(); itr++)
		cout << *itr
			<< " ";
}

Java:


package com.example.opengenous.unionOfArray;

import java.util.*;

public class SetImp {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        
          //Declare and Initialize two array objects.
		   Integer[] arr1= {18,17,13,12,14,11,11,10,12};
           Integer[] arr2= {16,13,14,13,15,11,12,10,19,10};
         
          //Create an empty set.
         Set<Integer> set = new TreeSet<Integer>();
         
         int m= arr1.length;
         int n= arr2.length;
         
         // Insert the first array elements into set object.
         for(int i=0; i<m; i++)
        	 set.add(i);
         
         // Insert the second array elements into set object.
         for(int i=0; i<m; i++)
        	 set.add(i);
             
        // Print some message if you want to print it.
        System.out.println("Number of elements after union operation: "+set.size());
        System.out.println("The union set of both arrays is :");
         
         // Print the elements of the set.
         for(int i: set) {
        	 System.out.print(i+" ");
         }
         System.out.println();    
	}
}

Output:

Number of elements after union operation: 10
The union set of both arrays is :
10 11 12 13 14 15 16 17 18 19 

Python:



#Declare and Initialize two array objects.
arr1= [18,17,13,12,14,11,11,10,12]
arr2= [16,13,14,13,15,11,12,10,19,10]

#Create an empty set.
from sortedcontainers import SortedSet
sortedSet= SortedSet()

#Insert the first array elements into set object.
for i in arr1:
 sortedSet.add(i)
 
#Insert the second array elements into set object. 
for i in arr2:
 sortedSet.add(i)

 #Print some message if you want to print it.
print("Number of elements after union operation: ", len(sortedSet))
print("The union set of both arrays is :")

#Print the set
print(sortedSet)

Output

Number of elements after union operation:  10
The union set of both arrays is :
SortedSet([10, 11, 12, 13, 14, 15, 16, 17, 18, 19])

Time Complexity:

A Set is an unordered and mutable collection of unique elements.But our goal is to get a sorted result. Again the time complexity of the algorithm has to be O(m+n).So we have implemented the following data structures in our code.
You can use any child class of set, the algorithm will remain the same. But maybe in some cases, you have to sort the result in descending order. In that case, time complexity will increase due to sorting.
Time complexity : O(m+n)

Using Map

Prerequisite :
i) C++ map
ii) Java TreeMap

Algorithm:

Step 1: Start
Step 2: Declare and Initialize two array objects.
Step 3: Create a map container.
Step 4: Create a vector to hold key values
Step 5: Store the array lengths in two different variables.(In the case of Java 4th and 5th step is not necessary.)
Step 5: Insert the first array elements into the map object and increment its occurrence.
Step 6: Insert the second array elements into the map object and increment its occurrence.
Step 7: Store the keys of the map into that vector and print the elements of the vector.

C++:


#include <bits/stdc++.h>
using namespace std;

// Driver Code
int main()
{
    //Declare and Initialize two array objects.
	int a[9] = {18,17,13,12,14,11,11,10,12};
	int b[10] = {16,13,14,13,15,11,12,10,19,10 };
    
    // Defining a map container map
	     map<int,int> map1;
         
    // take a vector to hold key values
	std::vector<int> key;
    
   // Inserting first array elements in map
	for (int i = 0; i < n; i++){
	   map1[a[i]]++;
	}
   
    //Inserting second array elements in map
    for (int i = 0; i < m; i++){
	    map1[b[i]]++;
	}
    
    cout << "Number of elements after union operation: " << map1.size() << endl;
	cout << "The union set of both arrays is :" << endl;
    
 // print all key values
 for(map<int,int>::iterator it = map1.begin(); it != map1.end(); ++it) {
    key.push_back(it->first);
    cout <<  it->first << " ";

}
}

Java:


package com.example.opengenous.unionOfArray;

import java.util.*;

public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        
		// Declare and Initialize two array objects.
		 Integer[] arr1= {18,17,13,12,14,11,11,10,12};
         Integer[] arr2= {16,13,14,13,15,11,12,10,19,10};
         
         // Defining a map container map
         Map<Integer,Integer>map= new TreeMap<>();
         
          //Inserting first array elements in map
         for(int i=0; i<arr1.length; i++) {
        	  map.put(arr1[i], map.getOrDefault(arr1[i],0)+1);
         }
         
         //Inserting first array elements in map
         for(int i=0; i<arr2.length; i++) {
        	 map.put(arr2[i], map.getOrDefault(arr2[i],0)+1);
         }
         
        // Print some messages if you want
        System.out.println("Number of elements after union operation: "+map.size());
        System.out.println("The union set of both arrays is :");
         
         // Print the key set of the map.
         for(int i:map.keySet()) {
        	 System.out.print(i+" ");
         }
         
         System.out.println();
	}

}

Output:

Number of elements after union operation: 10
The union set of both arrays is :
10 11 12 13 14 15 16 17 18 19 

Time Complexity:

A map contains values on the basis of key, i.e. key and value pair. Each key and value pair is known as an entry. A Map contains unique keys.We have got the solution using this feature.
You can use any child class of map, the algorithm will remain the same. But maybe in some cases, you have to sort the result in descending order. In that case, time complexity will increase due to sorting.
Time complexity : O(m+n)

Using Searching and sorting (Binary Search)

Algorithm:

Step 1: Start
Step 2: Declare an empty set globally.
Step 3: Declare and initialize two array objects.

Step 3: Store the array lengths in two different variables.
Step 4: Check the smallest length and sort the smaller array.
Step 5: Add all the elements of the smaller array in the set.
Step 6: For each element of the larger subarray check if the element present in the smaller array or not. (use binary search).
Step 7: If the element is not present, then add it into the set.
Step 8: Print all the elements in the set.

C++:


 #include <bits/stdc++.h>
using namespace std;

//Declare an empty set globally.
set<int> s;

// This method is for binary searching of each element of the larger array.
 bool hasFound(int num, int arr[],int len){
     
     int first=0;
     
     while(first<=len){
         
         int mid= (first+len)/2;
         
         if(arr[mid]==num)
           return true;
           
         else if(arr[mid]>num)
           len= mid-1;
           
         else
           first= mid+1;
     }
     
     return false;
 }


// This method is for adding the elements of the larger array.
void addAnother(int smallest[],int largest[],int smallestLen,int largestLen){
     
     for(int i=0; i<largestLen; i++){
         
         bool val= hasFound(largest[i],smallest,smallestLen);
         if(val==false)
          s.insert(largest[i]);
     }
    
 }
 
int main()
{
      
       int arr1[9] = {18,17,13,12,14,11,11,10,12};
       int arr2[10] = {16,13,14,13,15,11,12,10,19,10 };
	
      int m = sizeof(arr1) / sizeof(arr1[0]);
      int n = sizeof(arr2) / sizeof(arr2[0]);
    
    // Check which array length is smaller
    if(m>n){
      
       // sort the smaller  array
        sort(arr1,arr1+m);
        
      // Add the elements of smaller array into set
        for(int i: arr1)
          s.insert(i);
        
        addAnother(arr1,arr2,m,n);
    }
    
    else{
         // sort the smaller  array
        sort(arr2,arr2+n);
       
         // Add the elements of smaller array into set
        for(int i: arr2)
          s.insert(i);
        
        addAnother(arr2,arr1,n,m);
    }

      // Print the elements of the set.
    cout << "Number of elements after union operation: " << s.size() << endl;
	cout << "The union set of both arrays is :" << endl;
	
	for (auto itr = s.begin(); itr != s.end(); itr++)
		cout << *itr
			<< " "; 
    
} 

Java:


package com.example.opengenous.unionOfArray;

import java.util.*;

public class Main{
    
    //Declare an empty set globally.
    static  Set<Integer> union= new TreeSet<Integer>();
    
    public static void main(String[] args){
        
           int[] arr1= {18,17,13,12,14,11,11,10,12};
           int[]  arr2= {16,13,14,13,15,11,12,10,19,10};
         
        
            // Check which array length is smaller
         int minL= Math.min(arr1.length,arr2.length);
         
         if(minL==arr1.length){
         
              // sort the smaller  array
             Arrays.sort(arr1);
             
              // Add the elements of smaller array into set
              for(int i: arr1)
                union.add(i);
             
             addAnother(union,arr1,arr2);
            
         }
         else{
            
             // sort the smaller  array
              Arrays.sort(arr2);
             
            // Add the elements of smaller array into set
              for(int i: arr2)
                union.add(i);
                
              addAnother(union,arr2,arr1); 
         }
    }
    
    // This method is for adding the elements of the larger array.
    public static void addAnother(Set<Integer> union, int[] smallest,int[] largest){
        
          for(int i: largest){
              
              if(!hasFound(i,smallest))
                  union.add(i);
          }
          
        System.out.println("Number of elements after union operation: "+union.size());
        System.out.println("The union set of both arrays is :");
        
        for(int i: union)
          System.out.print(i+" ");
          
          System.out.println();
    }
    
    // This method is for binary searching of each element of the larger array.
    public static boolean hasFound(int num, int[] arr){
        
        int first=0, last= arr.length-1;
        
        while(first<=last){
            
            int mid= (first+last)/2;
            
            if(arr[mid]==num)
               return true;
               
            else if(arr[mid]> num)
              last= mid-1;
            
            else
              first= mid+1;
        }
        
       return false; 
    }
}

Output

Number of elements after union operation: 10
The union set of both arrays is :
10 11 12 13 14 15 16 17 18 19 

Time Complexity:
Time complexity of this algorithm is O((m+n)Logm, (m+n)Logn).This is one of the best approaches to array implementation.In the case of sorted arrays does not need to be performed the sorting operation.

Using two pointers

Algorithm
Step 1: Start
Step 2: Create an empty object of arraylist which will contain the result
Step 3: Take two pointers( which indicate the index) for each of the arrays.
Step 4: For each element of both of the arrays consider these three cases

case 1: When both of the array elements are equal
case 2: When the element of the first array is greater
case 3: When the element of the second array is greater

Step 6: For each case check these two conditions and perform the following action.

case 1: If the arraylist is not empty and the present element is not present in the list, add the element into the list.
case 2: If the arraylist is empty add the element into the list at last increment the index value of both arrays.

Step 7: Repeat steps 5 and 6 whether one of the pointers does not exceed the length of an array.
Step 8: Check if any of the elements in the array are still alive.

 Step 8.1: For the rest of the elements of first array repeat step 6.
 Step 8.2: For the rest of the elements of second array repeat step 6.     

Code:

package com.example.opengenous.unionOfArray;

import java.util.*;
public class Main{
    
    public static ArrayList<Integer> getUnion(int[]arr1, int[] arr2){
        
       
        ArrayList<Integer> list= new ArrayList<>();
      
   // Take two pointers for each of the arrays (Which indicate the index positions)
        int index1=0, index2=0;
       
     // for each element of both of the arrays consider these three cases

        while(index1<arr1.length && index2<arr2.length){
            
            // case 1: when both of the array elements are equal
            if(arr1[index1]== arr2[index2]){
                
       /* check whether the list is empty or not and also 
       check whether the elements are already present in the 
       list because the union does not contain duplicates.
       */
       
                if(list.size()>0 && !list.contains(arr1[index1])){
                    
                    list.add(arr1[index1]);
                }
                
                // if the list is empty , add the elements
                else if(list.size()==0){
                    list.add(arr1[index1]);
                }
                
                // increase the indexes value by 1
                index1++;
                index2++;
                
            }
            
            // When the element of the first array is greater
            else if(arr1[index1]<arr2[index2]){
                
                if(list.size()>0 && !list.contains(arr1[index1])){
                    
                    list.add(arr1[index1]);
                }
                
                else if(list.size()==0){
                    list.add(arr1[index1]);
                }
               
               index1++; 
            }
         
         //When the element of the second array is greater
         else{
            
             if( list.size()>0 && !list.contains(arr2[index2])){
                    
                    list.add(arr2[index2]);
                }
                
                else if( list.size()==0){
                    list.add(arr2[index2]);
                }
                
                index2++;
        }
        }
        
        // checking for the remaining element of first array
        while(index1<arr1.length){
            
               if(list.size()>0 && !list.contains(arr1[index1])){
                    
                    list.add(arr1[index1]);
                }
                
                else if(list.size()==0){
                    list.add(arr1[index1]);
                }
               
               index1++; 
        }
        
        // checking for remaining element of second array.
        while(index2<arr2.length){
            
            
             if(list.size()>0 && !list.contains(arr2[index2])){
                    
                    list.add(arr2[index2]);
                }
                
                else if(list.size()==0){
                    list.add(arr2[index2]);
                }
                
                index2++;
        }
        
        return list;
    }
    
    public static void main(String[] args){
        
           int[] arr1= {10,11,11,12,12,13,14,17,18};
           int[]  arr2= {10,10,11,12,13,13,14,15,16,19};
           
           ArrayList<Integer> list= getUnion(arr1,arr2);
           
        System.out.println("Number of elements after union operation: "+list.size());
        System.out.println("The union set of both arrays is :");
        
        for(int i: list)
          System.out.print(i+" ");
          
        System.out.println();
        
           int[] arr3= {1,1,2,2,3,4};
           int[]  arr4= {1,1,3};
           
           list= getUnion(arr3,arr4);
           
        System.out.println("Number of elements after union operation: "+list.size());
        System.out.println("The union set of both arrays is :");
        
        for(int i: list)
          System.out.print(i+" ");
          
        System.out.println();
    }
}

Output

Number of elements after union operation: 10
The union set of both arrays is :
10 11 12 13 14 15 16 17 18 19 
Number of elements after union operation: 4
The union set of both arrays is :
1 2 3 4

Time Complexity: O(max(m,n))
But space complexity is not flexible for this approach.

With this article at OpenGenus, you must have the complete idea of different approaches to find union of two arrays.