Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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.
