Union of Two-Sorted Arrays using Map
The idea of the approach is to build a Map and store the frequency of all the elements. Then insert all those elements whose frequency is greater than 0 in union array.
Below is the implementation of the above approach:
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the union of two arrays
vector<int> Unionarray(int arr1[], int arr2[], int n, int m)
{
map<int, int> map;
// Remove the duplicates from arr1[]
for (int i = 0; i < n; i++)
{
if (map.find(arr1[i]) != map.end())
{
map[arr1[i]]++;
}
else
{
map[arr1[i]] = 1;
}
}
// Remove duplicates from arr2[]
for (int i = 0; i < m; i++)
{
if (map.find(arr2[i]) != map.end())
{
map[arr2[i]]++;
}
else
{
map[arr2[i]] = 1;
}
}
// Loading set to vector
vector<int> list;
for (auto i : map)
{
list.push_back(i.first);
}
return list;
}
// Driver code
int main()
{
int arr1[] = { 1, 2, 2, 2, 3 };
int arr2[] = {2, 3, 3, 4, 5, 5 };
int n = sizeof(arr1)/sizeof(arr1[0]);
int m = sizeof(arr2)/sizeof(arr2[0]);
cout << "Union is :"<<endl;
// Function call
vector<int> uni = Unionarray(arr1, arr2, n, m);
for (auto i : uni)
{
cout << i << " ";
}
return 0;
}
// This code is contributed by Gaurav_Arora
// Java code to implement the approach
import java.io.*;
import java.util.*;
import java.util.HashMap;
class GFG {
// Function to return the union of two arrays
public static ArrayList<Integer>
Unionarray(int arr1[], int arr2[],
int n, int m)
{
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
// Remove the duplicates from arr1[]
for (int i =0;i<arr1.length;i++)
{
if(map.containsKey(arr1[i]))
{
map.put(arr1[i], map.get(arr1[i]) + 1);
}
else
{
map.put(arr1[i], 1);
}
}
// Remove duplicates from arr2[]
for (int i =0;i<arr2.length;i++)
{
if(map.containsKey(arr2[i]))
{
map.put(arr2[i], map.get(arr2[i]) + 1);
}
else
{
map.put(arr2[i], 1);
}
}
// Loading set to array list
ArrayList<Integer> list = new ArrayList<>();
for (int i : map.keySet())
{
list.add(i);;
}
return list;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 1, 2, 2, 2, 3 };
int arr2[] = { 2, 3, 3, 4, 5, 5 };
int n = arr1.length;
int m = arr2.length;
System.out.println("Union is :");
// Function call
ArrayList<Integer> uni
= Unionarray(arr1, arr2, n, m);
for (int i : uni) {
System.out.print(i + " ");
}
}
}
// This code is contributed by Aarti_Rathi
# Python code to implement the approach
from typing import List
def Unionarray(arr1: List[int], arr2: List[int], n: int, m: int) -> List[int]:
map = {}
# Remove the duplicates from arr1[]
for i in range(n):
if arr1[i] in map:
map[arr1[i]] += 1
else:
map[arr1[i]] = 1
# Remove duplicates from arr2[]
for i in range(m):
if arr2[i] in map:
map[arr2[i]] += 1
else:
map[arr2[i]] = 1
# Loading set to list
uni = list(map.keys())
return uni
# Driver code
arr1 = [1, 2, 2, 2, 3]
arr2 = [2, 3, 3, 4, 5, 5]
n = len(arr1)
m = len(arr2)
print("Union is :")
# Function call
uni = Unionarray(arr1, arr2, n, m)
for i in uni:
print(i, end=" ")
// C# code to implement the approach
using System;
using System.Collections;
using System.Collections.Generic;
public class GFG {
public static ArrayList
Unionarray(int[] arr1, int[] arr2, int n, int m)
{
Dictionary<int, int> map
= new Dictionary<int, int>();
// Remove the duplicates from arr1[]
for (int i = 0; i < n; i++) {
if (map.ContainsKey(arr1[i])) {
map[arr1[i]] += 1;
}
else {
map.Add(arr1[i], 1);
}
}
// Remove duplicates from arr2[]
for (int i = 0; i < m; i++) {
if (map.ContainsKey(arr2[i])) {
map[arr2[i]] += 1;
}
else {
map.Add(arr2[i], 1);
}
}
// Loading set to array list
ArrayList list = new ArrayList();
foreach(int i in map.Keys) { list.Add(i); }
return list;
}
static public void Main()
{
// Code
int[] arr1 = { 1, 2, 2, 2, 3 };
int[] arr2 = { 2, 3, 3, 4, 5, 5 };
int n = arr1.Length;
int m = arr2.Length;
Console.WriteLine("Union is :");
// Function call
ArrayList uni = Unionarray(arr1, arr2, n, m);
foreach(int i in uni) { Console.Write(i + " "); }
}
}
// This code is contributed by lokeshmvs21.
// Function to find the union of two arrays
function Unionarray(arr1, arr2) {
let map = {};
// Remove the duplicates from arr1[]
for (let i = 0; i < arr1.length; i++) {
if (arr1[i] in map) {
map[arr1[i]] += 1;
} else {
map[arr1[i]] = 1;
}
}Q
// Remove duplicates from arr2[]
for (let i = 0; i < arr2.length; i++) {
if (arr2[i] in map) {
map[arr2[i]] += 1;
} else {
map[arr2[i]] = 1;
}
}
// Loading set to list
let uni = Object.keys(map);
return uni;
}
// Driver code
let arr1 = [1, 2, 2, 2, 3];
let arr2 = [2, 3, 3, 4, 5, 5];
console.log("Union is :");
// Function call
let uni = Unionarray(arr1, arr2);
for (let i of uni) {
console.log(i + " ");
}
Output
Union is : 1 2 3 4 5
Time Complexity:O(m*log(m) + n*log(n)), where ‘m’ and ‘n’ are the size of the arrays
Auxiliary Space: O(m + n)
Union and Intersection of two sorted arrays
Given two sorted arrays, find their union and intersection.
Example:
Input: arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Output: Union : {1, 2, 3, 4, 5, 6, 7}
Intersection : {3, 5}Input: arr1[] = {2, 5, 6}
arr2[] = {4, 6, 8, 10}
Output: Union : {2, 4, 5, 6, 8, 10}
Intersection : {6}
Union of Two-Sorted Arrays using Sets
The idea of the approach is to build a Set and insert all the elements from both arrays into it. As a set stores only unique values, it will only keep all the unique values of both arrays.
Below is the implementation of the above approach:
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the union of two arrays
vector<int> Unionarray(int arr1[], int arr2[], int n, int m)
{
set<int> s;
// Remove the duplicates from arr1[]
for (int i = 0; i < n; i++) {
s.insert(arr1[i]);
}
// Remove duplicates from arr2[]
for (int i = 0; i < m; i++) {
s.insert(arr2[i]);
}
// Loading set to vector
vector<int> vec(s.begin(), s.end());
return vec;
}
// Driver code
int main()
{
int arr1[] = { 1, 2, 2, 2, 3 };
int arr2[] = { 2, 3, 3, 4, 5, 5 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int m = sizeof(arr2) / sizeof(arr2[0]);
// Function call
vector<int> uni = Unionarray(arr1, arr2, n, m);
for (int i : uni) {
cout << i << " ";
}
return 0;
}
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG {
// Function to return the union of two arrays
public static ArrayList<Integer>
Unionarray(int arr1[], int arr2[],
int n, int m)
{
TreeSet<Integer> set = new TreeSet<>();
// Remove the duplicates from arr1[]
for (int i : arr1)
set.add(i);
// Remove duplicates from arr2[]
for (int i : arr2)
set.add(i);
// Loading set to array list
ArrayList<Integer> list
= new ArrayList<>();
for (int i : set)
list.add(i);
return list;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 1, 2, 2, 2, 3 };
int arr2[] = { 2, 3, 3, 4, 5, 5 };
int n = arr1.length;
int m = arr2.length;
// Function call
ArrayList<Integer> uni
= Unionarray(arr1, arr2, n, m);
for (int i : uni) {
System.out.print(i + " ");
}
}
}
// Contributed by ARAVA SAI TEJA
# Python code to implement the approach
def Unionarray(arr1, arr2, n, m):
# Create a set to store unique elements from both arrays
set1 = set(arr1)
set2 = set(arr2)
# Merge both sets and convert back to list
result = list(set1.union(set2))
return result
# Driver code
if __name__ == "__main__":
arr1 = [1, 2, 2, 2, 3]
arr2 = [2, 3, 3, 4, 5, 5]
n = len(arr1)
m = len(arr2)
# Function call
uni = Unionarray(arr1, arr2, n, m)
for i in uni:
print(i, end=" ")
// Include namespace system
using System;
using System.Collections.Generic;
public class GFG
{
// Function to return the union of two arrays
public static List<int> Unionarray(int[] arr1, int[] arr2, int n, int m)
{
var set = new SortedSet<int>();
// Remove the duplicates from arr1[]
foreach (int i in arr1)
{ set.Add(i);
}
// Remove duplicates from arr2[]
foreach (int i in arr2)
{ set.Add(i);
}
// Loading set to array list
var list = new List<int>();
foreach (int i in set)
{ list.Add(i);
}
return list;
}
// Driver code
public static void Main(String[] args)
{
int[] arr1 = {1, 2, 2, 2, 3};
int[] arr2 = {2, 3, 3, 4, 5, 5};
var n = arr1.Length;
var m = arr2.Length;
// Function call
var uni = GFG.Unionarray(arr1, arr2, n, m);
foreach (int i in uni)
{
Console.Write(i.ToString() + " ");
}
}
}
// This code is contributed by sourabhdalal0001.
function unionArray(arr1, arr2)
{
// Create a set to store unique elements from both arrays
const set1 = new Set(arr1);
const set2 = new Set(arr2);
// Merge both sets and convert back to array
const result = [...new Set([...set1, ...set2])];
return result;
}
// Driver code
const arr1 = [1, 2, 2, 2, 3];
const arr2 = [2, 3, 3, 4, 5, 5];
// Function call
const uni = unionArray(arr1, arr2);
console.log(uni.join(' ')); // Output: 1 2 3 4 5
Output
1 2 3 4 5
Time Complexity: O(m*log(m) + n*log(n)), where ‘m’ and ‘n’ are the size of the arrays
Auxiliary Space: O(m + n)