Given two unsorted arrays that represent two sets (elements in every array are distinct), find the union and intersection of two arrays.
Example:
arr1[] = {7, 1, 5, 2, 3, 6}
arr2[] = {3, 8, 6, 20, 7}
Then your program should print Union as {1, 2, 3, 5, 6, 7, 8, 20} and Intersection as {3, 6, 7}. Note that the elements of union and intersection can be printed in any order.
Method 1 (Using Set):
Union of two arrays we can get with the Set data structure very easily. A set is a data structure that allows only the distinct elements in it. So, when we put the elements of both the array into the set we will get only the distinct elements that are equal to the union operation over the arrays. Let’s code it now –>
C++
#include <bits/stdc++.h>
using namespace std;
void getUnion(int a[], int n, int b[], int m)
{
set<int> s;
for (int i = 0; i < n; i++)
s.insert(a[i]);
for (int i = 0; i < m; i++)
s.insert(b[i]);
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 << " ";
}
int main()
{
int a[9] = { 1, 2, 5, 6, 2, 3, 5, 7, 3 };
int b[10] = { 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 };
getUnion(a, 9, b, 10);
}
|
C
#include <stdio.h>
#include <stdlib.h>
void getUnion(int a[], int n, int b[], int m)
{
int* s = (int*)malloc(sizeof(int) * (n + m));
int size = 0;
for (int i = 0; i < n; i++) {
if (!contains(s, size, a[i])) {
s[size++] = a[i];
}
}
for (int i = 0; i < m; i++) {
if (!contains(s, size, b[i])) {
s[size++] = b[i];
}
}
printf("Number of elements after union operation: %d\n",
size);
printf("The union set of both arrays is:\n");
for (int i = 0; i < size; i++) {
printf("%d ", s[i]);
}
free(s);
}
int contains(int arr[], int size, int x)
{
for (int i = 0; i < size; i++) {
if (arr[i] == x) {
return 1;
}
}
return 0;
}
int main()
{
int a[9] = { 1, 2, 5, 6, 2, 3, 5, 7, 3 };
int b[10] = { 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 };
getUnion(a, 9, b, 10);
return 0;
}
|
Java
import java.util.*;
class GFG {
static void getUnion(int a[], int n, int b[], int m)
{
HashSet<Integer> s = new HashSet<>();
for (int i = 0; i < n; i++)
s.add(a[i]);
for (int i = 0; i < m; i++)
s.add(b[i]);
System.out.print(
"Number of elements after union operation: "
+ s.size() + "\n");
System.out.print("The union set of both arrays is :"
+ "\n");
System.out.print(
s.toString()
+ " ");
}
public static void main(String[] args)
{
int a[] = { 1, 2, 5, 6, 2, 3, 5, 7, 3 };
int b[] = { 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 };
getUnion(a, 9, b, 10);
}
}
|
Python3
def getUnion(a, n, b, m):
s = set()
for i in range(n):
s.add(a[i])
for i in range(m):
s.add(b[i])
print("Number of elements after union operation: ", len(s), "")
print("The union set of both arrays is :" + "")
print(s, end="")
if __name__ == '__main__':
a = [1, 2, 5, 6, 2, 3, 5, 7, 3]
b = [2, 4, 5, 6, 8, 9, 4, 6, 5, 4]
getUnion(a, 9, b, 10)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
static void getUnion(int[] a, int n, int[] b, int m)
{
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++)
s.Add(a[i]);
for (int i = 0; i < m; i++)
s.Add(b[i]);
Console.Write(
"Number of elements after union operation: "
+ s.Count + "\n");
Console.Write("The union set of both arrays is :"
+ "\n");
foreach(int i in s) Console.Write(
i + " ");
}
public static void Main(String[] args)
{
int[] a = { 1, 2, 5, 6, 2, 3, 5, 7, 3 };
int[] b = { 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 };
getUnion(a, 9, b, 10);
}
}
|
Javascript
<script>
function getUnion(a, n, b, m) {
var s = new Set();
for (let i = 0; i < n; i++)
s.add(a[i]);
for (let i = 0; i < m; i++)
s.add(b[i]);
document.write(
"Number of elements after union operation: "
+ s.size + "<br>");
document.write("The union set of both arrays is :");
document.write("<br>");
var arr = [];
for (let itr of s)
arr.push(itr);
arr.sort(function (a, b) { return a - b; })
for (let i = 0; i < arr.length; i++) {
document.write(arr[i] + " ");
}
}
let a = [1, 2, 5, 6, 2, 3, 5, 7, 3];
let b = [2, 4, 5, 6, 8, 9, 4, 6, 5, 4];
getUnion(a, 9, b, 10);
</script>
|
Output
Number of elements after union operation: 9
The union set of both arrays is :
1 2 3 4 5 6 7 8 9
Time Complexity: O(m * log(m) + n * log(n))
Auxiliary Space: O(m + n)
Note: O(m + n) in case of Python because in python the set built-in method is quite different than that of C++ once, Python uses an hash map internally.
Method 2: We can improve performance of getUnion method by iterating over both the arrays for index from 0 to min(n, m)-1 adding all the elements in both the arrays to the set, and then iterate over the other array with the remaining elements and add them to the set.
C++
#include <bits/stdc++.h>
using namespace std;
void getUnion(int a[], int n, int b[], int m)
{
int min = (n < m) ? n : m;
set<int> s;
for (int i = 0; i < min; i++) {
s.insert(a[i]);
s.insert(b[i]);
}
if (n > m) {
for (int i = m; i < n; i++) {
s.insert(a[i]);
}
}
else if (n < m) {
for (int i = n; i < m; i++) {
s.insert(b[i]);
}
}
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 << " ";
}
int main()
{
int a[9] = { 1, 2, 5, 6, 2, 3, 5, 7, 3 };
int b[10] = { 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 };
getUnion(a, 9, b, 10);
}
|
C
#include <stdio.h>
#include <stdlib.h>
void getUnion(int a[], int n, int b[], int m)
{
int min = (n < m) ? n : m;
int i;
int* s = (int*)malloc((n + m) * sizeof(int));
int size = 0;
for (i = 0; i < min; i++) {
if (!contains(s, size, a[i])) {
s[size++] = a[i];
}
if (!contains(s, size, b[i])) {
s[size++] = b[i];
}
}
if (n > m) {
for (i = m; i < n; i++) {
if (!contains(s, size, a[i])) {
s[size++] = a[i];
}
}
}
else if (n < m) {
for (i = n; i < m; i++) {
if (!contains(s, size, b[i])) {
s[size++] = b[i];
}
}
}
printf("Number of elements after union operation: %d\n",
size);
printf("The union set of both arrays is:\n");
for (i = 0; i < size; i++) {
printf("%d ", s[i]);
}
}
int contains(int s[], int size, int element)
{
int i;
for (i = 0; i < size; i++) {
if (s[i] == element) {
return 1;
}
}
return 0;
}
int main()
{
int a[9] = { 1, 2, 5, 6, 2, 3, 5, 7, 3 };
int b[10] = { 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 };
getUnion(a, 9, b, 10);
return 0;
}
|
Java
import java.util.*;
class GFG {
static void getUnion(int a[], int n, int b[], int m)
{
int min = (n < m) ? n : m;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < min; i++) {
set.add(a[i]);
set.add(b[i]);
}
if (n > m) {
for (int i = m; i < n; i++) {
set.add(a[i]);
}
}
else if (n < m) {
for (int i = n; i < m; i++) {
set.add(b[i]);
}
}
System.out.println(
"Number of elements after union operation: "
+ set.size());
System.out.println(
"The union set of both arrays is :");
System.out.print(set.toString());
}
public static void main(String[] args)
{
int a[] = { 1, 2, 5, 6, 2, 3, 5, 7, 3 };
int b[] = { 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 };
getUnion(a, 9, b, 10);
}
}
|
Python3
def getUnion(a, n, b, m):
hs = set()
if(n < m):
min = n
else:
min = m
for i in range(0, min):
hs.add(a[i])
hs.add(b[i])
if(n > m):
for i in range(m, n):
hs.add(a[i])
else:
if(n < m):
for i in range(m, n):
hs.add(b[i])
print("Number of elements after union operation: ", len(hs))
print("The union set of both arrays is :")
for i in hs:
print(i, end=" ")
print("\n")
a = [1, 2, 5, 6, 2, 3, 5, 7, 3]
b = [2, 4, 5, 6, 8, 9, 4, 6, 5, 4]
n1 = len(a)
n2 = len(b)
getUnion(a, n1, b, n2)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
static void getUnion(int[] a, int n, int[] b, int m)
{
int min = (n < m) ? n : m;
HashSet<int> set = new HashSet<int>();
for (int i = 0; i < min; i++) {
set.Add(a[i]);
set.Add(b[i]);
}
if (n > m) {
for (int i = m; i < n; i++) {
set.Add(a[i]);
}
}
else if (n < m) {
for (int i = n; i < m; i++) {
set.Add(b[i]);
}
}
Console.WriteLine(
"Number of elements after union operation: "
+ set.Count);
Console.WriteLine(
"The union set of both arrays is :[");
foreach(int x in set) Console.Write(x + ", ");
Console.Write("]");
}
public static void Main(String[] args)
{
int[] a = { 1, 2, 5, 6, 2, 3, 5, 7, 3 };
int[] b = { 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 };
getUnion(a, 9, b, 10);
}
}
|
Javascript
<script>
function getUnion(a , n , b , m) {
var min = (n < m) ? n : m;
var set = new Set();
for (i = 0; i < min; i++) {
set.add(a[i]);
set.add(b[i]);
}
if (n > m) {
for (i = m; i < n; i++) {
set.add(a[i]);
}
} else if (n < m) {
for (i = n; i < m; i++) {
set.add(b[i]);
}
}
document.write("Number of elements after union operation: " + set.size);
document.write("<br/>The union set of both arrays is :<br/>");
set.forEach (function(value) {
document.write(value+" ");
})
}
var a = [ 1, 2, 5, 6, 2, 3, 5, 7, 3 ];
var b = [ 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 ];
getUnion(a, 9, b, 10);
</script>
|
Output
Number of elements after union operation: 9
The union set of both arrays is :
1 2 3 4 5 6 7 8 9
Time Complexity: O( max(m,n) )
Auxiliary Space: O(max(m, n))
Method 2: (Using map data structure)
From the knowledge of data structures, we know that map stores distinct keys only. So if we insert any key appearing more than one time it gets stored only once. The idea is to insert both the arrays in one common map which would then store the distinct elements of both arrays (union of both the array).
Below is the implementation of the above method:
C++
#include <bits/stdc++.h>
using namespace std;
void printUnion(int* a, int n, int* b, int m)
{
map<int, int> mp;
for (int i = 0; i < n; i++)
mp.insert({ a[i], i });
for (int i = 0; i < m; i++)
mp.insert({ b[i], i });
cout << "The union set of both arrays is :" << endl;
for (auto itr = mp.begin(); itr != mp.end(); itr++)
cout << itr->first
<< " ";
}
int main()
{
int a[7] = { 1, 2, 5, 6, 2, 3, 5 };
int b[9] = { 2, 4, 5, 6, 8, 9, 4, 6, 5 };
printUnion(a, 7, b, 9);
}
|
C
#include <stdio.h>
#include <stdlib.h>
void printUnion(int* a, int n, int* b, int m)
{
int* mp = (int*)malloc((n + m) * sizeof(int));
int count = 0;
for (int i = 0; i < n; i++) {
mp[count++] = a[i];
}
for (int i = 0; i < m; i++) {
int found = 0;
for (int j = 0; j < count; j++) {
if (b[i] == mp[j]) {
found = 1;
break;
}
}
if (!found) {
mp[count++] = b[i];
}
}
printf("The union set of both arrays is:\n");
for (int i = 0; i < count; i++) {
printf("%d ", mp[i]);
}
printf("\n");
free(mp);
}
int main()
{
int a[7] = { 1, 2, 5, 6, 2, 3, 5 };
int b[9] = { 2, 4, 5, 6, 8, 9, 4, 6, 5 };
printUnion(a, 7, b, 9);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static void printUnion(int[] a, int n, int[] b, int m)
{
Map<Integer, Integer> mp
= new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
mp.put(a[i], i);
}
for (int i = 0; i < m; i++) {
mp.put(b[i], i);
}
System.out.println(
"The union set of both arrays is :");
for (Map.Entry mapElement : mp.entrySet()) {
System.out.print(mapElement.getKey() + " ");
}
}
public static void main(String[] args)
{
int a[] = { 1, 2, 5, 6, 2, 3, 5 };
int b[] = { 2, 4, 5, 6, 8, 9, 4, 6, 5 };
printUnion(a, 7, b, 9);
}
}
|
Python3
def printUnion(a, n, b, m):
mp = {}
for i in range(n):
mp[a[i]] = i
for i in range(m):
mp[b[i]] = i
print("The union set of both arrays is : ")
for key in mp.keys():
print(key, end=" ")
a = [1, 2, 5, 6, 2, 3, 5]
b = [2, 4, 5, 6, 8, 9, 4, 6, 5]
printUnion(a, 7, b, 9)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
static void printUnion(int[] a, int n, int[] b, int m)
{
Dictionary<int, int> mp
= new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
if (!mp.ContainsKey(a[i]))
mp.Add(a[i], i);
}
for (int i = 0; i < m; i++) {
if (!mp.ContainsKey(b[i]))
mp.Add(b[i], i);
}
Console.WriteLine(
"The union set of both arrays is :");
foreach(KeyValuePair<int, int> mapElement in mp)
{
Console.Write(mapElement.Key + " ");
}
}
public static void Main(String[] args)
{
int[] a = { 1, 2, 5, 6, 2, 3, 5 };
int[] b = { 2, 4, 5, 6, 8, 9, 4, 6, 5 };
printUnion(a, 7, b, 9);
}
}
|
Javascript
<script>
function printUnion(a , n, b , m)
{
var mp = new Map();
for(var i = 0; i < n; i++)
{
mp.set(a[i], i);
}
for(var i = 0; i < m; i++)
{
mp.set(b[i], i);
}
document.write("The union set of both arrays is :<br/>");
for(var key of mp.keys())
{
document.write(key + " ");
}
}
var a = [ 1, 2, 5, 6, 2, 3, 5 ];
var b = [ 2, 4, 5, 6, 8, 9, 4, 6, 5 ];
printUnion(a, 7, b, 9);
</script>
|
Output
The union set of both arrays is :
1 2 3 4 5 6 8 9
Time Complexity: O(m * log(m) + n * log(n)), for using map data structure.
Auxiliary Space: O(m + n)
*This method is suggested by Vinay Verma
Method 3 (Naive)
Union:
- Initialize union U as empty.
- Copy all elements of the first array to U.
- Do the following for every element x of the second array:
- If x is not present in the first array, then copy x to U.
- Return U.
Intersection:
- Initialize intersection I as empty.
- Do the following for every element x of the first array
- If x is present in the second array, then copy x to I.
- Return I.
The time complexity of this method is O(mn) for both operations. Here m and n are numbers of elements in arr1[] and arr2[] respectively.
However, above method works only for distinct elements in input arrays.
Method 4 (Use Sorting)
- Sort arr1[] and arr2[]. This step takes O(mLogm + nLogn) time.
- Use O(m + n) algorithms to find the union and intersection of two sorted arrays.
The overall time complexity of this method is O(mLogm + nLogn).
C++
#include<bits/stdc++.h>
using namespace std;
void printUnion(vector<int> arr1, vector<int> arr2, int m, int n){
sort(arr1.begin(), arr1.end());
sort(arr2.begin(), arr2.end());
int i = 0;
int j = 0;
while(i < m && j < n){
if(arr1[i] < arr2[j]){
cout<<arr1[i]<<" ";
i++;
}
else if(arr2[j] < arr1[i]){
cout<<arr2[j]<<" ";
j++;
}
else{
cout<<arr2[j]<<" ";
i++;
j++;
}
}
while(i < m){
cout<<arr1[i]<<" ";
i++;
}
while(j < n){
cout<<arr2[j]<<" ";
j++;
}
}
void printIntersection(vector<int> arr1, vector<int> arr2, int m, int n){
sort(arr1.begin(), arr1.end());
sort(arr2.begin(), arr2.end());
int i = 0;
int j = 0;
while(i < m && j < n){
if(arr1[i] < arr2[j]){
i++;
}
else if (arr2[j] < arr1[i]){
j++;
}
else{
cout<<arr2[j]<<" ";
i++;
j++;
}
}
}
int main(){
vector<int> arr1 = { 7, 1, 5, 2, 3, 6 };
vector<int> arr2 = { 3, 8, 6, 20, 7 };
int m = arr1.size();
int n = arr2.size();
cout<<"Union of two arrays is : ";
printUnion(arr1, arr2, m, n);
cout<<endl<<"Intersection of two array is : ";
printIntersection(arr1, arr2, m, n);
}
|
C
#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
void printUnion(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
qsort(arr1, m, sizeof(int), cmpfunc);
qsort(arr2, n, sizeof(int), cmpfunc);
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
printf("%d ", arr1[i]);
i++;
}
else if (arr2[j] < arr1[i]) {
printf("%d ", arr2[j]);
j++;
}
else {
printf("%d ", arr2[j]);
i++;
j++;
}
}
while (i < m) {
printf("%d ", arr1[i]);
i++;
}
while (j < n) {
printf("%d ", arr2[j]);
j++;
}
}
void printIntersection(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
qsort(arr1, m, sizeof(int), cmpfunc);
qsort(arr2, n, sizeof(int), cmpfunc);
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i++;
}
else if (arr2[j] < arr1[i]) {
j++;
}
else {
printf("%d ", arr2[j]);
i++;
j++;
}
}
}
int main()
{
int arr1[] = { 7, 1, 5, 2, 3, 6 };
int arr2[] = { 3, 8, 6, 20, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
printf("Union of two arrays is: ");
printUnion(arr1, arr2, m, n);
printf("\nIntersection of two arrays is: ");
printIntersection(arr1, arr2, m, n);
return 0;
}
|
Java
import java.util.Arrays;
class Main {
public static void printUnion(int[] arr1, int[] arr2, int m, int n) {
Arrays.sort(arr1);
Arrays.sort(arr2);
int i = 0;
int j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
System.out.println(arr1[i]);
i += 1;
} else if (arr2[j] < arr1[i]) {
System.out.println(arr2[j]);
j += 1;
} else {
System.out.println(arr2[j]);
j += 1;
i += 1;
}
}
while (i < m) {
System.out.println(arr1[i]);
i += 1;
}
while (j < n) {
System.out.println(arr2[j]);
j += 1;
}
}
public static void printIntersection(int[] arr1, int[] arr2, int m, int n) {
Arrays.sort(arr1);
Arrays.sort(arr2);
int i = 0;
int j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i += 1;
} else if (arr2[j] < arr1[i]) {
j += 1;
} else {
System.out.println(arr2[j]);
j += 1;
i += 1;
}
}
}
public static void main(String[] args) {
int[] arr1 = {7, 1, 5, 2, 3, 6};
int[] arr2 = {3, 8, 6, 20, 7};
int m = arr1.length;
int n = arr2.length;
System.out.println("Union of two arrays is : ");
printUnion(arr1, arr2, m, n);
System.out.println("Intersection of two arrays is : ");
printIntersection(arr1, arr2, m, n);
}
}
|
Python
def printUnion(arr1, arr2, m, n):
arr1.sort()
arr2.sort()
i = 0
j = 0
while(i < m and j < n):
if(arr1[i] < arr2[j]):
print(arr1[i])
i += 1
elif (arr2[j] < arr1[i]):
print(arr2[j])
j += 1
else:
print(arr2[j])
j += 1
i += 1
while(i < m):
print(arr1[i])
i += 1
while(j < n):
print(arr2[j])
j += 1
def printIntersection(arr1, arr2, m, n):
arr1.sort()
arr2.sort()
i = 0
j = 0
while(i < m and j < n):
if(arr1[i] < arr2[j]):
i += 1
elif(arr2[j] < arr1[i]):
j += 1
else:
print(arr2[j])
j += 1
i += 1
arr1 = [ 7, 1, 5, 2, 3, 6 ]
arr2 = [ 3, 8, 6, 20, 7 ]
m = len(arr1)
n = len(arr2)
print("Union of two arrays is : ")
printUnion(arr1, arr2, m, n)
print("Intersection of two arrays is : ")
printIntersection(arr1, arr2, m, n)
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
public class Program {
public static void
PrintUnion(List<int> arr1, List<int> arr2, int m, int n)
{
arr1.Sort();
arr2.Sort();
int i = 0;
int j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
Console.Write(arr1[i] + " ");
i++;
}
else if (arr2[j] < arr1[i]) {
Console.Write(arr2[j] + " ");
j++;
}
else {
Console.Write(arr2[j] + " ");
i++;
j++;
}
}
while (i < m) {
Console.Write(arr1[i] + " ");
i++;
}
while (j < n) {
Console.Write(arr2[j] + " ");
j++;
}
}
public static void PrintIntersection(List<int> arr1,
List<int> arr2,
int m, int n)
{
arr1.Sort();
arr2.Sort();
int i = 0;
int j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i++;
}
else if (arr2[j] < arr1[i]) {
j++;
}
else {
Console.Write(arr2[j] + " ");
i++;
j++;
}
}
}
public static void Main()
{
List<int> arr1 = new List<int>{ 7, 1, 5, 2, 3, 6 };
List<int> arr2 = new List<int>{ 3, 8, 6, 20, 7 };
int m = arr1.Count();
int n = arr2.Count();
Console.Write("Union of two arrays is : ");
PrintUnion(arr1, arr2, m, n);
Console.Write("\nIntersection of two array is : ");
PrintIntersection(arr1, arr2, m, n);
}
}
|
Javascript
function printUnion(arr1, arr2, m, n){
arr1.sort(function(a, b){return a-b;});
arr2.sort(function(a,b){return a-b;});
let i = 0;
let j = 0;
while(i < m && j < n){
if(arr1[i] < arr2[j])
document.write(arr1[i++] + " ");
else if(arr2[j] < arr1[i])
document.write(arr2[j++] + " ");
else{
document.write(arr2[j++] + " ");
i++;
}
}
while(i < m)
document.write(arr1[i++] + " ");
while(j < n)
document.write(arr2[j++] + " ");
return 0;
}
function printIntersection(arr1, arr2, m, n){
arr1.sort(function(a, b){return a-b;});
arr2.sort(function(a,b){return a-b;});
let i = 0;
let j = 0;
while(i < m && j < n){
if(arr1[i] < arr2[j])
i++;
else if(arr2[j] < arr1[i])
j++;
else{
document.write(arr2[j++] + " ");
i++;
}
}
}
let arr1 = [ 7, 1, 5, 2, 3, 6 ];
let arr2 = [ 3, 8, 6, 20, 7 ];
let m = arr1.length;
let n = arr2.length;
document.write("Union of two arrays is : ");
printUnion(arr1, arr2, m, n);
document.write("Intersection of two arrays is : ");
printIntersection(arr1, arr2, m, n);
|
Method 5 (Use Sorting and Searching)
Union:
- Initialize union U as empty.
- Find smaller m and n and sort the smaller array.
- Copy the smaller array to U.
- For every element x of a larger array, do the following
- Binary Search x in the smaller array. If, x is not present, then copy it to U.
- Return U.
Intersection:
- Initialize intersection I as empty.
- Find smaller of m and n and sort the smaller array.
- For every element x of a larger array, do the following
- Binary Search x in the smaller array. If x is present, then copy it to I.
- Return I.
Time complexity of this method is min(mLogm + nLogm, mLogn + nLogn) which can also be written as O((m+n)Logm, (m+n)Logn). This approach works much better than the previous approach when the difference between the sizes of two arrays is significant.
Thanks to use_the_force for suggesting this method in a comment here.
Below is the implementation of this method. However, this method also works only for distinct elements in input arrays.
C++
#include <algorithm>
#include <iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int x);
void printUnion(int arr1[], int arr2[], int m, int n)
{
if (m > n) {
int* tempp = arr1;
arr1 = arr2;
arr2 = tempp;
int temp = m;
m = n;
n = temp;
}
sort(arr1, arr1 + m);
for (int i = 0; i < m; i++)
cout << arr1[i] << " ";
for (int i = 0; i < n; i++)
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
cout << arr2[i] << " ";
}
void printIntersection(int arr1[], int arr2[], int m, int n)
{
if (m > n) {
int* tempp = arr1;
arr1 = arr2;
arr2 = tempp;
int temp = m;
m = n;
n = temp;
}
sort(arr1, arr1 + m);
for (int i = 0; i < n; i++)
if (binarySearch(arr1, 0, m - 1, arr2[i]) != -1)
cout << arr2[i] << " ";
}
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main()
{
int arr1[] = { 7, 1, 5, 2, 3, 6 };
int arr2[] = { 3, 8, 6, 20, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
cout << "Union of two arrays is " << endl;
printUnion(arr1, arr2, m, n);
cout << endl;
cout << "Intersection of two arrays is " << endl;
printIntersection(arr1, arr2, m, n);
return 0;
}
|
Java
import java.util.Arrays;
class UnionAndIntersection {
void printUnion(int arr1[], int arr2[], int m, int n)
{
if (m > n) {
int tempp[] = arr1;
arr1 = arr2;
arr2 = tempp;
int temp = m;
m = n;
n = temp;
}
Arrays.sort(arr1);
for (int i = 0; i < m; i++)
System.out.print(arr1[i] + " ");
for (int i = 0; i < n; i++) {
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
System.out.print(arr2[i] + " ");
}
}
void printIntersection(int arr1[], int arr2[], int m,
int n)
{
if (m > n) {
int tempp[] = arr1;
arr1 = arr2;
arr2 = tempp;
int temp = m;
m = n;
n = temp;
}
Arrays.sort(arr1);
for (int i = 0; i < n; i++) {
if (binarySearch(arr1, 0, m - 1, arr2[i]) != -1)
System.out.print(arr2[i] + " ");
}
}
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
public static void main(String[] args)
{
UnionAndIntersection u_i
= new UnionAndIntersection();
int arr1[] = { 7, 1, 5, 2, 3, 6 };
int arr2[] = { 3, 8, 6, 20, 7 };
int m = arr1.length;
int n = arr2.length;
System.out.println("Union of two arrays is ");
u_i.printUnion(arr1, arr2, m, n);
System.out.println("");
System.out.println(
"Intersection of two arrays is ");
u_i.printIntersection(arr1, arr2, m, n);
}
}
|
Python3
def printUnion(arr1, arr2, m, n):
if (m > n):
tempp = arr1
arr1 = arr2
arr2 = tempp
temp = m
m = n
n = temp
arr1.sort()
for i in range(0, m):
print(arr1[i], end=" ")
for i in range(0, n):
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1):
print(arr2[i], end=" ")
def printIntersection(arr1, arr2, m, n):
if (m > n):
tempp = arr1
arr1 = arr2
arr2 = tempp
temp = m
m = n
n = temp
arr1.sort()
for i in range(0, n):
if (binarySearch(arr1, 0, m - 1, arr2[i]) != -1):
print(arr2[i], end=" ")
def binarySearch(arr, l, r, x):
if (r >= l):
mid = int(l + (r - l)/2)
if (arr[mid] == x):
return mid
if (arr[mid] > x):
return binarySearch(arr, l, mid - 1, x)
return binarySearch(arr, mid + 1, r, x)
return -1
arr1 = [7, 1, 5, 2, 3, 6]
arr2 = [3, 8, 6, 20, 7]
m = len(arr1)
n = len(arr2)
print("Union of two arrays is ")
printUnion(arr1, arr2, m, n)
print("\nIntersection of two arrays is ")
printIntersection(arr1, arr2, m, n)
|
C#
using System;
class GFG {
static void printUnion(int[] arr1, int[] arr2, int m,
int n)
{
if (m > n) {
int[] tempp = arr1;
arr1 = arr2;
arr2 = tempp;
int temp = m;
m = n;
n = temp;
}
Array.Sort(arr1);
for (int i = 0; i < m; i++)
Console.Write(arr1[i] + " ");
for (int i = 0; i < n; i++) {
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
Console.Write(arr2[i] + " ");
}
}
static void printIntersection(int[] arr1, int[] arr2,
int m, int n)
{
if (m > n) {
int[] tempp = arr1;
arr1 = arr2;
arr2 = tempp;
int temp = m;
m = n;
n = temp;
}
Array.Sort(arr1);
for (int i = 0; i < n; i++) {
if (binarySearch(arr1, 0, m - 1, arr2[i]) != -1)
Console.Write(arr2[i] + " ");
}
}
static int binarySearch(int[] arr, int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
static public void Main()
{
int[] arr1 = { 7, 1, 5, 2, 3, 6 };
int[] arr2 = { 3, 8, 6, 20, 7 };
int m = arr1.Length;
int n = arr2.Length;
Console.WriteLine("Union of two arrays is ");
printUnion(arr1, arr2, m, n);
Console.WriteLine("");
Console.WriteLine("Intersection of two arrays is ");
printIntersection(arr1, arr2, m, n);
}
}
|
Javascript
<script>
function binarySearch(arr, l, r, x)
{
if (r >= l) {
let mid = l + Math.floor((r - l) / 2);
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
function printUnion(arr1, arr2, m, n)
{
if (m > n) {
let tempp = arr1;
arr1 = arr2;
arr2 = tempp;
let temp = m;
m = n;
n = temp;
}
arr1.sort((a, b) => a - b);
for (let i = 0; i < m; i++)
document.write(arr1[i] + " ");
for (let i = 0; i < n; i++)
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
document.write(arr2[i] + " ");
}
function printIntersection(arr1, arr2, m, n)
{
if (m > n) {
let tempp = arr1;
arr1 = arr2;
arr2 = tempp;
let temp = m;
m = n;
n = temp;
}
arr1.sort((a, b) => a - b);
for (let i = 0; i < n; i++)
if (binarySearch(arr1, 0, m - 1, arr2[i]) != -1)
document.write(arr2[i] + " ");
}
let arr1 = [ 7, 1, 5, 2, 3, 6 ];
let arr2 = [ 3, 8, 6, 20, 7 ];
let m = arr1.length;
let n = arr2.length;
document.write("Union of two arrays is <br>");
printUnion(arr1, arr2, m, n);
document.write("<br>Intersection of two arrays is<br>");
printIntersection(arr1, arr2, m, n);
</script>
|
PHP
<?php
function printUnion($arr1, $arr2, $m, $n)
{
if ($m > $n)
{
$tempp = $arr1;
$arr1 = $arr2;
$arr2 = $tempp;
$temp = $m;
$m = $n;
$n = $temp;
}
sort($arr1);
for ($i = 0; $i < $m; $i++)
echo $arr1[$i]." ";
for ($i = 0; $i < $n; $i++)
if (binarySearch($arr1, 0, $m - 1, $arr2[$i]) == -1)
echo $arr2[$i]." ";
}
function printIntersection($arr1, $arr2, $m, $n)
{
if ($m > $n)
{
$tempp = $arr1;
$arr1 = $arr2;
$arr2 = $tempp;
$temp = $m;
$m = $n;
$n = $temp;
}
sort($arr1);
for ($i = 0; $i < $n; $i++)
if (binarySearch($arr1, 0, $m - 1, $arr2[$i]) != -1)
echo $arr2[$i]." ";
}
function binarySearch($arr, $l, $r,$x)
{
if ($r >= $l)
{
$mid = (int)($l + ($r - $l)/2);
if ($arr[$mid] == $x) return $mid;
if ($arr[$mid] > $x)
return binarySearch($arr, $l, $mid - 1, $x);
return binarySearch($arr, $mid + 1, $r, $x);
}
return -1;
}
$arr1 = array(7, 1, 5, 2, 3, 6);
$arr2 = array(3, 8, 6, 20, 7);
$m = count($arr1);
$n = count($arr2);
echo "Union of two arrays is \n";
printUnion($arr1, $arr2, $m, $n);
echo "\nIntersection of two arrays is \n";
printIntersection($arr1, $arr2, $m, $n);
?>
|
Output
Union of two arrays is 3 6 7 8 20 1 5 2
Intersection of two arrays is 7 3 6
Another Approach (When elements in the array may not be distinct) :
C++
#include <bits/stdc++.h>
using namespace std;
void intersection(int a[], int b[], int n, int m)
{
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] > b[j]) {
j++;
}
else if (b[j] > a[i]) {
i++;
}
else {
cout << a[i] << " ";
i++;
j++;
}
}
}
int main()
{
int a[] = { 1, 3, 2, 3, 3, 4, 5, 5, 6 };
int b[] = { 3, 3, 5 };
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
sort(a, a + n);
sort(b, b + m);
intersection(a, b, n, m);
}
|
Java
import java.io.*;
import java.util.Arrays;
class GFG {
static void intersection(int a[], int b[], int n, int m)
{
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] > b[j]) {
j++;
}
else if (b[j] > a[i]) {
i++;
}
else {
System.out.print(a[i] + " ");
i++;
j++;
}
}
}
public static void main(String[] args)
{
int a[] = { 1, 3, 2, 3, 4, 5, 5, 6 };
int b[] = { 3, 3, 5 };
int n = a.length;
int m = b.length;
Arrays.sort(a);
Arrays.sort(b);
intersection(a, b, n, m);
}
}
|
Python3
def intersection(a, b, n, m):
i = 0
j = 0
while (i < n and j < m):
if (a[i] > b[j]):
j += 1
else:
if (b[j] > a[i]):
i += 1
else:
print(a[i], end=" ")
i += 1
j += 1
if __name__ == "__main__":
a = [1, 3, 2, 3, 4, 5, 5, 6]
b = [3, 3, 5]
n = len(a)
m = len(b)
a.sort()
b.sort()
intersection(a, b, n, m)
|
C#
using System;
class GFG {
static void intersection(int[] a, int[] b, int n, int m)
{
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] > b[j]) {
j++;
}
else if (b[j] > a[i]) {
i++;
}
else {
Console.Write(a[i] + " ");
i++;
j++;
}
}
}
public static void Main()
{
int[] a = { 1, 3, 2, 3, 4, 5, 5, 6 };
int[] b = { 3, 3, 5 };
int n = a.Length;
int m = b.Length;
Array.Sort(a);
Array.Sort(b);
intersection(a, b, n, m);
}
}
|
Javascript
<script>
function intersection(a,b,n,m)
{
let i = 0, j = 0;
while (i < n && j < m)
{
if (a[i] > b[j])
{
j++;
}
else if (b[j] > a[i])
{
i++;
}
else
{
document.write(a[i] + " ");
i++;
j++;
}
}
}
let a = [1, 3, 2, 3, 4, 5, 5, 6 ];
let b = [3, 3, 5 ]
let n = a.length;
let m = b.length;
a.sort();
b.sort();
intersection(a, b, n, m);
</script>
|
PHP
<?php
function intersection($a, $b, $n, $m)
{
$i = 0; $j = 0;
while ($i < $n && $j < $m)
{
if ($a[$i] > $b[$j])
{
$j++;
}
else
if ($b[$j] > $a[$i])
{
$i++;
}
else
{
echo($a[$i] . " ");
$i++;
$j++;
}
}
}
$a = array(1, 3, 2, 3, 4, 5, 5, 6);
$b = array(3, 3, 5);
$n = sizeof($a);
$m = sizeof($b);
sort($a);
sort($b);
intersection($a, $b, $n, $m);
?>
|
Time Complexity: O(max(m*log(m), n*log(n)) + min(m, n) )
Auxiliary Space: O(1)
Thanks, Sanny Kumar for suggesting the above method.
Method 6(Without using hashing or any predefined library like sets or maps and works even for both repeated and distant elements)
First of all we sort both arrays and proceed as below:
Union
- Iterate in while loop until any one array is finished.
- In each iteration we look for smaller in both arrays and we print it and increment its pointer only if it is not same as the last element printed in union.
- After we finish while we iterate the remaining of two array in the similar way as above and print the union.
Intersection
- Iterate in while loop till any of the one array is finished.
- In each iteration we look for smaller of the two elements from both the array and increase its pointer because it will not be in other list, hence not part of intersection.
- For intersection,ff both the elements are equal we print it and increment both pointer only if it is not same as the last element printed in intersection.
C++
#include <bits/stdc++.h>
using namespace std;
void Union(int a[], int b[], int n, int m)
{
int* result = new int[n + m];
int index = 0;
int left = 0, right = 0;
while (left < n && right < m) {
if (a[left] < b[right]) {
if (index != 0
&& a[left] == result[index - 1]) {
left++;
}
else {
result[index] = a[left];
left++;
index++;
}
}
else {
if (index != 0
&& b[right] == result[index - 1]) {
right++;
}
else {
result[index] = b[right];
right++;
index++;
}
}
}
while (left < n) {
if (index != 0 && a[left] == result[index - 1]) {
left++;
}
else {
result[index] = a[left];
left++;
index++;
}
}
while (right < m) {
if (index != 0 && b[right] == result[index - 1]) {
right++;
}
else {
result[index] = b[right];
right++;
index++;
}
}
cout << "Union: ";
for (int k = 0; k < index; k++)
cout << result[k] << " ";
cout << endl;
};
void intersection(int a[], int b[], int n, int m)
{
int i = 0, j = 0, k = 0;
int* result = new int[n + m];
while (i < n && j < m) {
if (a[i] < b[j])
i++;
else if (a[i] > b[j])
j++;
else {
if (k != 0 && a[i] == result[k - 1]) {
i++;
j++;
}
else {
result[k] = a[i];
i++;
j++;
k++;
}
}
}
cout << "Intersection: ";
for (int x = 0; x < k; x++)
cout << result[x] << " ";
cout << endl;
}
int main()
{
int a[] = { 1, 3, 2, 3, 3, 4, 5, 5, 6 };
int b[] = { 3, 3, 5 };
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
sort(a, a + n);
sort(b, b + m);
Union(a, b, n, m);
intersection(a, b, n, m);
}
|
Java
import java.util.*;
class GFG {
static void Union(int[] a, int[] b, int n, int m)
{
int[] result = new int[n + m];
int index = 0;
int left = 0, right = 0;
while (left < n && right < m) {
if (a[left] < b[right]) {
if (index != 0
&& a[left] == result[index - 1]) {
left++;
}
else {
result[index] = a[left];
left++;
index++;
}
}
else {
if (index != 0
&& b[right] == result[index - 1]) {
right++;
}
else {
result[index] = b[right];
right++;
index++;
}
}
}
while (left < n) {
if (index != 0
&& a[left] == result[index - 1]) {
left++;
}
else {
result[index] = a[left];
left++;
index++;
}
}
while (right < m) {
if (index != 0
&& b[right] == result[index - 1]) {
right++;
}
else {
result[index] = b[right];
right++;
index++;
}
}
System.out.print("Union: ");
for (int k = 0; k < index; k++)
System.out.print(result[k] + " ");
System.out.println("");
}
static void intersection(int[] a, int[] b, int n, int m)
{
int i = 0, j = 0, k = 0;
int[] result = new int[n + m];
while (i < n && j < m) {
if (a[i] < b[j])
i++;
else if (a[i] > b[j])
j++;
else {
if (k != 0 && a[i] == result[k - 1]) {
i++;
j++;
}
else {
result[k] = a[i];
i++;
j++;
k++;
}
}
}
System.out.print("Intersection: ");
for (int x = 0; x < k; x++)
System.out.print(result[x] + " ");
System.out.println();
}
public static void main(String[] args)
{
int[] a = { 1, 3, 2, 3, 3, 4, 5, 5, 6 };
int[] b = { 3, 3, 5 };
int n = a.length;
int m = b.length;
Arrays.sort(a);
Arrays.sort(b);
Union(a, b, n, m);
intersection(a, b, n, m);
}
}
|
Python3
def Union(a, b, n, m):
result = [0 for _ in range(n + m)]
index, left, right = 0, 0, 0
while left < n and right < m:
if (a[left] < b[right]):
if(index != 0 and a[left] == result[index-1]):
left += 1
else:
result[index] = a[left]
left += 1
index += 1
else:
if (index != 0 and b[right] == result[index-1]):
right += 1
else:
result[index] = b[right]
right += 1
index += 1
while(left < n):
if(index != 0 and a[left] == result[index-1]):
left += 1
else:
result[index] = a[left]
left += 1
index += 1
while(right < m):
if(index != 0 and b[right] == result[index - 1]):
right += 1
else:
result[index] = b[right]
right += 1
index += 1
print("Union:", *result[:index])
def intersection(a, b, n, m):
i, j, k = 0, 0, 0
result = [0 for _ in range(n + m)]
while i < n and j < m:
if a[i] < b[j]:
i += 1
elif a[i] > b[j]:
j += 1
else:
if k != 0 and a[i] == result[k - 1]:
i += 1
j += 1
else:
result[k] = a[i]
i += 1
j += 1
k += 1
print("Intersection:", *result[:k])
a = [1, 3, 2, 3, 3, 4, 5, 5, 6]
b = [3, 3, 5]
n, m = len(a), len(b)
a.sort()
b.sort()
Union(a, b, n, m)
intersection(a, b, n, m)
|
C#
using System;
using System.Collections.Generic;
class GFG {
static void Union(int[] a, int[] b, int n, int m)
{
int[] result = new int[n + m];
int index = 0;
int left = 0, right = 0;
while (left < n && right < m) {
if (a[left] < b[right]) {
if (index != 0
&& a[left] == result[index - 1]) {
left++;
}
else {
result[index] = a[left];
left++;
index++;
}
}
else {
if (index != 0
&& b[right] == result[index - 1]) {
right++;
}
else {
result[index] = b[right];
right++;
index++;
}
}
}
while (left < n) {
if (index != 0
&& a[left] == result[index - 1]) {
left++;
}
else {
result[index] = a[left];
left++;
index++;
}
}
while (right < m) {
if (index != 0
&& b[right] == result[index - 1]) {
right++;
}
else {
result[index] = b[right];
right++;
index++;
}
}
Console.Write("Union: ");
for (int k = 0; k < index; k++)
Console.Write(result[k] + " ");
Console.WriteLine("");
}
static void intersection(int[] a, int[] b, int n, int m)
{
int i = 0, j = 0, k = 0;
int[] result = new int[n + m];
while (i < n && j < m) {
if (a[i] < b[j])
i++;
else if (a[i] > b[j])
j++;
else {
if (k != 0 && a[i] == result[k - 1]) {
i++;
j++;
}
else {
result[k] = a[i];
i++;
j++;
k++;
}
}
}
Console.Write("Intersection: ");
for (int x = 0; x < k; x++)
Console.Write(result[x] + " ");
Console.WriteLine();
}
public static void Main(string[] args)
{
int[] a = { 1, 3, 2, 3, 3, 4, 5, 5, 6 };
int[] b = { 3, 3, 5 };
int n = a.Length;
int m = b.Length;
Array.Sort(a);
Array.Sort(b);
Union(a, b, n, m);
intersection(a, b, n, m);
}
}
|
Javascript
function Union(a, b, n, m)
{
let result = new Array(n + m);
let index = 0;
let left = 0, right = 0;
while (left < n && right < m) {
if (a[left] < b[right]) {
if (index != 0
&& a[left] == result[index - 1]) {
left++;
}
else {
result[index] = a[left];
left++;
index++;
}
}
else {
if (index != 0
&& b[right] == result[index - 1]) {
right++;
}
else {
result[index] = b[right];
right++;
index++;
}
}
}
while (left < n) {
if (index != 0 && a[left] == result[index - 1]) {
left++;
}
else {
result[index] = a[left];
left++;
index++;
}
}
while (right < m) {
if (index != 0 && b[right] == result[index - 1]) {
right++;
}
else {
result[index] = b[right];
right++;
index++;
}
}
process.stdout.write("Union: ");
for (var k = 0; k < index; k++)
process.stdout.write(result[k] + " ");
process.stdout.write("\n");
}
function intersection(a, b, n, m)
{
let i = 0, j = 0, k = 0;
let result = new Array(n + m);
while (i < n && j < m) {
if (a[i] < b[j])
i++;
else if (a[i] > b[j])
j++;
else {
if (k != 0 && a[i] == result[k - 1]) {
i++;
j++;
}
else {
result[k] = a[i];
i++;
j++;
k++;
}
}
}
process.stdout.write("Intersection: ");
for (var x = 0; x < k; x++)
process.stdout.write(result[x] + " ");
process.stdout.write("\n");
}
let a = [ 1, 3, 2, 3, 3, 4, 5, 5, 6 ];
let b = [ 3, 3, 5 ];
let n = a.length;
let m = b.length;
a.sort();
b.sort();
Union(a, b, n, m);
intersection(a, b, n, m);
|
Output
Union: 1 2 3 4 5 6
Intersection: 3 5
Method 7 (Use Hashing)
Union
- Initialize an empty hash set hs.
- Iterate through the first array and put every element of the first array in the set S.
- Repeat the process for the second array.
- Print the set hs.
Intersection
- Initialize an empty set hs.
- Iterate through the first array and put every element of the first array in the set S.
- For every element x of the second array, do the following :
Search x in the set hs. If x is present, then print it. Time complexity of this method is ?(m+n) under the assumption that hash table search and insert operations take ?(1) time.
Below is the implementation of the above idea:
C++
#include <bits/stdc++.h>
using namespace std;
void printUnion(int arr1[], int arr2[], int n1, int n2)
{
set<int> hs;
for (int i = 0; i < n1; i++)
hs.insert(arr1[i]);
for (int i = 0; i < n2; i++)
hs.insert(arr2[i]);
for (auto it = hs.begin(); it != hs.end(); it++)
cout << *it << " ";
cout << endl;
}
void printIntersection(int arr1[], int arr2[], int n1,
int n2)
{
set<int> hs;
for (int i = 0; i < n1; i++)
hs.insert(arr1[i]);
for (int i = 0; i < n2; i++)
if (hs.find(arr2[i]) != hs.end()) {
hs.erase(arr2[i]);
cout << arr2[i] << " ";
}
}
int main()
{
int arr1[] = { 7, 1, 5, 2, 3, 6 };
int arr2[] = { 3, 8, 6, 20, 7 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
printUnion(arr1, arr2, n1, n2);
printIntersection(arr1, arr2, n1, n2);
return 0;
}
|
Java
import java.util.HashSet;
class Test {
static void printUnion(int arr1[], int arr2[])
{
HashSet<Integer> hs = new HashSet<>();
for (int i = 0; i < arr1.length; i++)
hs.add(arr1[i]);
for (int i = 0; i < arr2.length; i++)
hs.add(arr2[i]);
System.out.println(hs);
}
static void printIntersection(int arr1[], int arr2[])
{
HashSet<Integer> hs = new HashSet<>();
HashSet<Integer> hs1 = new HashSet<>();
for (int i = 0; i < arr1.length; i++)
hs.add(arr1[i]);
for (int i = 0; i < arr2.length; i++)
if (hs.contains(arr2[i]))
System.out.print(arr2[i] + " ");
}
public static void main(String[] args)
{
int arr1[] = { 7, 1, 5, 2, 3, 6 };
int arr2[] = { 3, 8, 6, 20, 7 };
System.out.println("Union of two arrays is : ");
printUnion(arr1, arr2);
System.out.println(
"Intersection of two arrays is : ");
printIntersection(arr1, arr2);
}
}
|
Python
def printUnion(arr1, arr2, n1, n2):
hs = set()
for i in range(0, n1):
hs.add(arr1[i])
for i in range(0, n2):
hs.add(arr2[i])
print("Union:")
for i in hs:
print(i, end=" ")
print("\n")
def printIntersection(arr1, arr2, n1, n2):
hs = set()
for i in range(0, n1):
hs.add(arr1[i])
print("Intersection:")
for i in range(0, n2):
if arr2[i] in hs:
print(arr2[i], end=" ")
arr1 = [7, 1, 5, 2, 3, 6]
arr2 = [3, 8, 6, 20, 7]
n1 = len(arr1)
n2 = len(arr2)
printUnion(arr1, arr2, n1, n2)
printIntersection(arr1, arr2, n1, n2)
|
C#
using System;
using System.Linq;
using System.Collections.Generic;
class GFG {
static void printUnion(int[] arr1, int[] arr2)
{
HashSet<int> hs = new HashSet<int>();
for (int i = 0; i < arr1.Length; i++)
hs.Add(arr1[i]);
for (int i = 0; i < arr2.Length; i++)
hs.Add(arr2[i]);
Console.WriteLine(string.Join(", ", hs));
}
static void printIntersection(int[] arr1, int[] arr2)
{
HashSet<int> hs = new HashSet<int>();
for (int i = 0; i < arr1.Length; i++)
hs.Add(arr1[i]);
for (int i = 0; i < arr2.Length; i++)
if (hs.Contains(arr2[i]))
Console.Write(arr2[i] + " ");
}
static void Main()
{
int[] arr1 = { 7, 1, 5, 2, 3, 6 };
int[] arr2 = { 3, 8, 6, 20, 7 };
Console.WriteLine("Union of two arrays is : ");
printUnion(arr1, arr2);
Console.WriteLine(
"\nIntersection of two arrays is : ");
printIntersection(arr1, arr2);
}
}
|
Javascript
<script>
function printUnion(arr1 , arr2) {
var hs = new Set();
for (i = 0; i < arr1.length; i++)
hs.add(arr1[i]);
for (i = 0; i < arr2.length; i++)
hs.add(arr2[i]);
for(var k of hs)
document.write(k+" ");
}
function printIntersection(arr1 , arr2) {
var hs = new Set();
var hs1 = new Set();
for (i = 0; i < arr1.length; i++)
hs.add(arr1[i]);
for (var i = 0; i < arr2.length; i++)
if (hs.has(arr2[i]))
document.write(arr2[i] + " ");
}
var arr1 = [ 7, 1, 5, 2, 3, 6 ];
var arr2 = [ 3, 8, 6, 20, 7 ];
document.write("Union of two arrays is :<br/> ");
printUnion(arr1, arr2);
document.write("<br/>Intersection of two arrays is : <br/>");
printIntersection(arr1, arr2);
</script>
|
Output
1 2 3 5 6 7 8 20
3 6 7
This method is contributed by Ankur Singh.
The time complexity of this method is O(m+n) under the assumption that hash table search and insert operations take O(1) time.
Method 8 (Kind of hashing technique without using any predefined Java Collections)
- Initialize the array with a size of m+n
- Fill first array value in a resultant array by doing hashing(to find appropriate position)
- Repeat for the second array
- While doing hashing if a collision happens increment the position in a recursive way
Below is the implementation of the above code:
C++
#include <bits/stdc++.h>
using namespace std;
void printUnion(int v, int ans[], int zero)
{
int zero1 = 0;
cout << "\nUnion : ";
for (int i = 0; i < v; i++) {
if ((zero == 0 && ans[i] == 0)
|| (ans[i] == 0 && zero1 > 0))
continue;
if (ans[i] == 0)
zero1++;
cout << ans[i] << ",";
}
}
void placeValue(int a[], int ans[], int i, int p, int v)
{
p = p % v;
if (ans[p] == 0)
ans[p] = a[i];
else {
if (ans[p] == a[i])
cout << a[i] << ",";
else {
p = p + 1;
placeValue(a, ans, i, p, v);
}
}
}
void placeZeros(int v, int ans[], int zero)
{
if (zero == 2) {
cout << "0" << endl;
int d[] = { 0 };
placeValue(d, ans, 0, 0, v);
}
if (zero == 1) {
int d[] = { 0 };
placeValue(d, ans, 0, 0, v);
}
}
int iterateArray(int a[], int v, int ans[], int i)
{
if (a[i] != 0) {
int p = a[i] % v;
placeValue(a, ans, i, p, v);
}
else
return 1;
return 0;
}
void findPosition(int a[], int b[], int n1, int n2)
{
int v = (n1 + n2);
int ans[v];
for (int i = 0; i < v; i++) {
ans[i] = 0;
}
int zero1 = 0;
int zero2 = 0;
cout << "Intersection : ";
for (int i = 0; i < n1; i++)
zero1 = iterateArray(a, v, ans, i);
for (int j = 0; j < n2; j++)
zero2 = iterateArray(b, v, ans, j);
int zero = zero1 + zero2;
placeZeros(v, ans, zero);
printUnion(v, ans, zero);
}
int main()
{
int arr1[] = { 7, 1, 5, 2, 3, 6 };
int arr2[] = { 3, 8, 6, 20, 7 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
findPosition(arr1, arr2, n1, n2);
return 0;
}
|
Java
public class UnsortedIntersectionUnion {
public void findPosition(int a[], int b[])
{
int v = (a.length + b.length);
int ans[] = new int[v];
int zero1 = 0;
int zero2 = 0;
System.out.print("Intersection : ");
for (int i = 0; i < a.length; i++)
zero1 = iterateArray(a, v, ans, i);
for (int j = 0; j < b.length; j++)
zero2 = iterateArray(b, v, ans, j);
int zero = zero1 + zero2;
placeZeros(v, ans, zero);
printUnion(v, ans, zero);
}
private void printUnion(int v, int[] ans, int zero)
{
int zero1 = 0;
System.out.print("\nUnion : ");
for (int i = 0; i < v; i++) {
if ((zero == 0 && ans[i] == 0)
|| (ans[i] == 0 && zero1 > 0))
continue;
if (ans[i] == 0)
zero1++;
System.out.print(ans[i] + ",");
}
}
private void placeZeros(int v, int[] ans, int zero)
{
if (zero == 2) {
System.out.println("0");
int d[] = { 0 };
placeValue(d, ans, 0, 0, v);
}
if (zero == 1) {
int d[] = { 0 };
placeValue(d, ans, 0, 0, v);
}
}
private int iterateArray(int[] a, int v, int[] ans,
int i)
{
if (a[i] != 0) {
int p = a[i] % v;
placeValue(a, ans, i, p, v);
}
else
return 1;
return 0;
}
private void placeValue(int[] a, int[] ans, int i,
int p, int v)
{
p = p % v;
if (ans[p] == 0)
ans[p] = a[i];
else {
if (ans[p] == a[i])
System.out.print(a[i] + ",");
else {
p = p + 1;
placeValue(a, ans, i, p, v);
}
}
}
public static void main(String args[])
{
int a[] = { 7, 1, 5, 2, 3, 6 };
int b[] = { 3, 8, 6, 20, 7 };
UnsortedIntersectionUnion uiu
= new UnsortedIntersectionUnion();
uiu.findPosition(a, b);
}
}
|
Python3
def findPosition(a, b):
v = len(a) + len(b)
ans = [0]*v
zero1 = zero2 = 0
print("Intersection :", end=" ")
for i in range(len(a)):
zero1 = iterateArray(a, v, ans, i)
for j in range(len(b)):
zero2 = iterateArray(b, v, ans, j)
zero = zero1 + zero2
placeZeros(v, ans, zero)
printUnion(v, ans, zero)
def printUnion(v, ans, zero):
zero1 = 0
print("\nUnion :", end=" ")
for i in range(v):
if ((zero == 0 and ans[i] == 0) or
(ans[i] == 0 and zero1 > 0)):
continue
if (ans[i] == 0):
zero1 += 1
print(ans[i], end=",")
def placeZeros(v, ans, zero):
if (zero == 2):
print("0")
d = [0]
placeValue(d, ans, 0, 0, v)
if (zero == 1):
d = [0]
placeValue(d, ans, 0, 0, v)
def iterateArray(a, v, ans, i):
if (a[i] != 0):
p = a[i] % v
placeValue(a, ans, i, p, v)
else:
return 1
return 0
def placeValue(a, ans, i, p, v):
p = p % v
if (ans[p] == 0):
ans[p] = a[i]
else:
if (ans[p] == a[i]):
print(a[i], end=",")
else:
p = p + 1
placeValue(a, ans, i, p, v)
a = [7, 1, 5, 2, 3, 6]
b = [3, 8, 6, 20, 7]
findPosition(a, b)
|
C#
using System;
class UnsortedIntersectionUnion {
public void findPosition(int[] a, int[] b)
{
int v = (a.Length + b.Length);
int[] ans = new int[v];
int zero1 = 0;
int zero2 = 0;
Console.Write("Intersection : ");
for (int i = 0; i < a.Length; i++)
zero1 = iterateArray(a, v, ans, i);
for (int j = 0; j < b.Length; j++)
zero2 = iterateArray(b, v, ans, j);
int zero = zero1 + zero2;
placeZeros(v, ans, zero);
printUnion(v, ans, zero);
}
private void printUnion(int v, int[] ans, int zero)
{
int zero1 = 0;
Console.Write("\nUnion : ");
for (int i = 0; i < v; i++) {
if ((zero == 0 && ans[i] == 0)
|| (ans[i] == 0 && zero1 > 0))
continue;
if (ans[i] == 0)
zero1++;
Console.Write(ans[i] + ",");
}
}
private void placeZeros(int v, int[] ans, int zero)
{
if (zero == 2) {
Console.WriteLine("0");
int[] d = { 0 };
placeValue(d, ans, 0, 0, v);
}
if (zero == 1) {
int[] d = { 0 };
placeValue(d, ans, 0, 0, v);
}
}
private int iterateArray(int[] a, int v, int[] ans,
int i)
{
if (a[i] != 0) {
int p = a[i] % v;
placeValue(a, ans, i, p, v);
}
else
return 1;
return 0;
}
private void placeValue(int[] a, int[] ans, int i,
int p, int v)
{
p = p % v;
if (ans[p] == 0)
ans[p] = a[i];
else {
if (ans[p] == a[i])
Console.Write(a[i] + ",");
else {
p = p + 1;
placeValue(a, ans, i, p, v);
}
}
}
public static void Main()
{
int[] a = { 7, 1, 5, 2, 3, 6 };
int[] b = { 3, 8, 6, 20, 7 };
UnsortedIntersectionUnion uiu
= new UnsortedIntersectionUnion();
uiu.findPosition(a, b);
}
}
|
Javascript
<script>
function findPosition(a , b) {
var v = (a.length + b.length);
var ans = Array(v).fill(0);
var zero1 = 0;
var zero2 = 0;
document.write("Intersection : ");
for (var i = 0; i < a.length; i++)
zero1 = iterateArray(a, v, ans, i);
for (var j = 0; j < b.length; j++)
zero2 = iterateArray(b, v, ans, j);
var zero = zero1 + zero2;
placeZeros(v, ans, zero);
printUnion(v, ans, zero);
}
function printUnion(v, ans , zero) {
var zero1 = 0;
document.write("<br/>Union : ");
for (i = 0; i < v; i++) {
if ((zero == 0 && ans[i] == 0) || (ans[i] == 0 && zero1 > 0))
continue;
if (ans[i] == 0)
zero1++;
document.write(ans[i] + ",");
}
}
function placeZeros(v, ans , zero) {
if (zero == 2) {
document.write("0");
var d = [ 0 ];
placeValue(d, ans, 0, 0, v);
}
if (zero == 1) {
var d = [ 0 ];
placeValue(d, ans, 0, 0, v);
}
}
function iterateArray(a , v, ans , i) {
if (a[i] != 0) {
var p = a[i] % v;
placeValue(a, ans, i, p, v);
} else
return 1;
return 0;
}
function placeValue(a, ans , i , p , v) {
p = p % v;
if (ans[p] == 0)
ans[p] = a[i];
else {
if (ans[p] == a[i])
document.write(a[i] + ",");
else {
p = p + 1;
placeValue(a, ans, i, p, v);
}
}
}
var a = [ 7, 1, 5, 2, 3, 6 ];
var b = [ 3, 8, 6, 20, 7 ];
findPosition(a, b);
</script>
|
Output
Intersection : 3,6,7,
Union : 1,2,3,5,6,7,8,20,
C++
#include <bits/stdc++.h>
using namespace std;
void printUnion(int arr1[], int arr2[], int n1, int n2)
{
set<int> s;
for (int i = 0; i < n1; i++) {
s.insert(arr1[i]);
}
for (int i = 0; i < n2; i++) {
s.insert(arr2[i]);
}
cout << "Union:" << endl;
for (auto itr = s.begin(); itr != s.end(); itr++)
cout << *itr << " ";
cout << endl;
}
void printIntersection(int arr1[], int arr2[], int n1,
int n2)
{
set<int> s;
for (int i = 0; i < n1; i++) {
s.insert(arr1[i]);
}
cout << "Intersection:" << endl;
for (int i = 0; i < n2; i++) {
if (s.count(arr2[i])) {
cout << arr2[i] << " ";
}
}
cout << endl;
}
int main()
{
int arr1[] = { 7, 1, 5, 2, 3, 6 };
int arr2[] = { 3, 8, 6, 20, 7 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
printUnion(arr1, arr2, n1, n2);
printIntersection(arr1, arr2, n1, n2);
}
|
Java
import java.util.*;
public class GFG {
static void printUnion(int arr1[], int arr2[], int n1,
int n2)
{
Set<Integer> s = new HashSet<Integer>();
for (int i = 0; i < n1; i++) {
s.add(arr1[i]);
}
for (int i = 0; i < n2; i++) {
s.add(arr2[i]);
}
System.out.println("Union");
for (int itr : s)
System.out.print(itr + " ");
System.out.println();
}
static void printIntersection(int arr1[], int arr2[],
int n1, int n2)
{
Set<Integer> s = new HashSet<Integer>();
for (int i = 0; i < n1; i++) {
s.add(arr1[i]);
}
System.out.println("Intersection");
for (int i = 0; i < n2; i++) {
if (s.contains(arr2[i])) {
System.out.print(arr2[i] + " ");
}
}
System.out.println();
}
public static void main(String args[])
{
int arr1[] = { 7, 1, 5, 2, 3, 6 };
int arr2[] = { 3, 8, 6, 20, 7 };
int n1 = arr1.length;
int n2 = arr2.length;
printUnion(arr1, arr2, n1, n2);
printIntersection(arr1, arr2, n1, n2);
}
}
|
Python3
def printUnion(arr1, arr2, n1, n2):
hs = set()
for i in range(0, n1):
hs.add(arr1[i])
for i in range(0, n2):
hs.add(arr2[i])
print("Union:")
for i in hs:
print(i, end=" ")
print("\n")
def printIntersection(arr1, arr2, n1, n2):
hs = set()
for i in range(0, n1):
hs.add(arr1[i])
print("Intersection:")
for i in range(0, n2):
if arr2[i] in hs:
print(arr2[i], end=" ")
arr1 = [7, 1, 5, 2, 3, 6]
arr2 = [3, 8, 6, 20, 7]
n1 = len(arr1)
n2 = len(arr2)
printUnion(arr1, arr2, n1, n2)
printIntersection(arr1, arr2, n1, n2)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
static void printUnion(int[] arr1, int[] arr2, int n1,
int n2)
{
SortedSet<int> s = new SortedSet<int>();
for (int i = 0; i < n1; i++) {
s.Add(arr1[i]);
}
for (int i = 0; i < n2; i++) {
s.Add(arr2[i]);
}
Console.WriteLine("Union");
foreach(var itr in s)
Console.Write(itr + " ");
Console.WriteLine();
}
static void printIntersection(int[] arr1, int[] arr2,
int n1, int n2)
{
SortedSet<int> s = new SortedSet<int>();
for (int i = 0; i < n1; i++) {
s.Add(arr1[i]);
}
Console.WriteLine("Intersection");
for (int i = 0; i < n2; i++) {
if (s.Contains(arr2[i])) {
Console.Write(arr2[i] + " ");
}
}
Console.WriteLine();
}
public static void Main(string[] args)
{
int[] arr1 = { 7, 1, 5, 2, 3, 6 };
int[] arr2 = { 3, 8, 6, 20, 7 };
int n1 = arr1.Length;
int n2 = arr2.Length;
printUnion(arr1, arr2, n1, n2);
printIntersection(arr1, arr2, n1, n2);
}
}
|
Javascript
function printUnion(arr1, arr2, n1, n2)
{
let s = new Set();
for (var i = 0; i < n1; i++)
{
s.add(arr1[i]);
}
for (var i = 0; i < n2; i++)
{
s.add(arr2[i]);
}
console.log("Union:");
for (var itr of s)
process.stdout.write(itr + " ");
console.log();
}
function printIntersection(arr1, arr2, n1, n2)
{
let s = new Set();
for (var i = 0; i < n1; i++)
{
s.add(arr1[i]);
}
console.log("Intersection:");
for (var i = 0; i < n2; i++)
{
if(s.has(arr2[i]))
{
process.stdout.write(arr2[i] + " ");
}
}
console.log;
}
let arr1 = [ 7, 1, 5, 2, 3, 6 ];
let arr2 = [ 3, 8, 6, 20, 7 ];
let n1 = arr1.length;
let n2 = arr2.length;
printUnion(arr1, arr2, n1, n2);
printIntersection(arr1, arr2, n1, n2);
|
Output
Union:
1 2 3 5 6 7 8 20
Intersection:
3 6 7
See the following post for sorted arrays. Find Union and Intersection of two sorted arrays
Method – 9 : using union() and intersection() built-in set methods –
In this approach we will use some built-in set methods like union() and intersection() to achieve the same.
Stepwise explanation of the approach –
Union Operation –
- Step : 1 – Firstly we will convert the provided arrays into sets.
- Step – 2 – Then we will find their union using the union() method.
- Step – 3 – Then we will use another variable of type set to store the union of them.
- Step – 4 – If needed we will then sort the set stored in that variable otherwise print it as it is.
Intersection Operation –
- Step – 1 – Firstly we will convert the provided arrays into sets.
- Step – 2 – Then we will find their intersection using the intersection() method.
- Step – 3 – Then we will use another variable of type set to store the intersection of them.
- Step – 4 – If needed we will then sort the set stored in that variable otherwise print it as it is. As set is an unordered data structure so the order might not be the same everytime, as we want to sorted version so we might need to use the sort() method after performing the intersection or union operation on the resultant array.
Below is the Code –
C++
#include <iostream>
#include <set>
int main() {
std::set<int> arr1 = {7, 1, 5, 2, 3, 6};
std::set<int> arr2 = {3, 8, 6, 20, 7};
std::set<int> unionSet;
for (int num : arr1) {
unionSet.insert(num);
}
for (int num : arr2) {
unionSet.insert(num);
}
std::set<int> intersectionSet;
for (int num : arr1) {
if (arr2.find(num) != arr2.end()) {
intersectionSet.insert(num);
}
}
std::cout << "Set elements after union:" << std::endl;
for (int num : unionSet) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "Set elements after intersection:" << std::endl;
for (int num : intersectionSet) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
|
Java
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
public class SetOperations {
public static void main(String[] args) {
Set<Integer> arr1 = new HashSet<>();
arr1.add(7);
arr1.add(1);
arr1.add(5);
arr1.add(2);
arr1.add(3);
arr1.add(6);
Set<Integer> arr2 = new HashSet<>();
arr2.add(3);
arr2.add(8);
arr2.add(6);
arr2.add(20);
arr2.add(7);
Set<Integer> union = new TreeSet<>(arr1);
union.addAll(arr2);
HashSet<Integer> intersection = new HashSet<>(arr1);
intersection.retainAll(arr2);
System.out.println("Set elements after union:");
for (int element : union) {
System.out.print(element + " ");
}
System.out.println();
System.out.println("Set elements after intersection:");
for (int element : intersection) {
System.out.print(element + " ");
}
System.out.println();
}
}
|
Python3
arr1 = set([7, 1, 5, 2, 3, 6])
arr2 = set([3, 8, 6, 20, 7])
union = arr1.union(arr2)
intersection = arr1.intersection(arr2)
print("Set elements after union \n", *union)
print("Set elements after intersection\n", *intersection)
|
C#
using System;
using System.Collections.Generic;
class SetOperations
{
static void Main()
{
SortedSet<int> arr1 = new SortedSet<int> { 7, 1, 5, 2, 3, 6 };
SortedSet<int> arr2 = new SortedSet<int> { 3, 8, 6, 20, 7 };
SortedSet<int> unionSet = new SortedSet<int>(arr1);
unionSet.UnionWith(arr2);
SortedSet<int> intersectionSet = new SortedSet<int>(arr1);
intersectionSet.IntersectWith(arr2);
Console.WriteLine("Set elements after union:");
foreach (int num in unionSet)
{
Console.Write(num + " ");
}
Console.WriteLine();
Console.WriteLine("Set elements after intersection:");
foreach (int num in intersectionSet)
{
Console.Write(num + " ");
}
Console.WriteLine();
}
}
|
Javascript
const arr1 = new Set([7, 1, 5, 2, 3, 6]);
const arr2 = new Set([3, 8, 6, 20, 7]);
const unionSet = new Set([...arr1, ...arr2]);
const intersectionSet = new Set([...arr1].filter(num => arr2.has(num)));
console.log("Set elements after union:");
for (const num of unionSet) {
console.log(num);
}
console.log("Set elements after intersection:");
for (const num of intersectionSet) {
console.log(num);
}
|
Output
Set elements after union
1 2 3 5 6 7 8 20
Set elements after intersection
3 6 7
Time Complexity – O(n+m) # Where n is the size of arr1 and m is the size of arr2. Both for union as well as intersection.
Space Complexity – O(n+m) # As two new variables are being used to store the result, n denotes the number of elements after union and m denotes the number of elements after intersection.
Please Login to comment...