Intersection of Two-Sorted Arrays using Sets
The idea is to add elements of first array in a set. Then, iterate through the second array and check for each element whether it exists in the set. If an element is present in set, it means the element is present in both arrays and the element is added to the output, and its occurrence in the set is removed to avoid duplicates in the output.
Below is the implementation of the above approach :
#include <bits/stdc++.h>
using namespace std;
// Function to find the intersection
// of two arrays
vector<int> Intersection(int arr1[], int arr2[], int n,
int m)
{
set<int> st;
// Removing duplicates from first array
for (int i = 0; i < n; i++)
st.insert(arr1[i]);
vector<int> res;
// Avoiding duplicates and adding intersections
for (int i = 0; i < m; i++) {
if (st.find(arr2[i]) != st.end()) {
res.push_back(arr2[i]);
st.erase(arr2[i]);
}
}
return res;
}
// Driver code
int main()
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int m = sizeof(arr2) / sizeof(arr2[0]);
// Function call
vector<int> inter = Intersection(arr1, arr2, n, m);
for (int i : inter)
cout << i << " ";
return 0;
}
import java.util.HashSet;
import java.util.ArrayList;
public class Intersection {
// Function to find the intersection of two arrays
public static ArrayList<Integer> findIntersection(int[] arr1, int[] arr2) {
HashSet<Integer> set = new HashSet<>();
// Removing duplicates from the first array
for (int num : arr1) {
set.add(num);
}
ArrayList<Integer> result = new ArrayList<>();
// Avoiding duplicates and adding intersections
for (int num : arr2) {
if (set.contains(num)) {
result.add(num);
set.remove(num);
}
}
return result;
}
// Driver code
public static void main(String[] args) {
int[] arr1 = { 1, 2, 4, 5, 6 };
int[] arr2 = { 2, 3, 5, 7 };
// Function call
ArrayList<Integer> intersection = findIntersection(arr1, arr2);
for (int num : intersection) {
System.out.print(num + " ");
}
}
}
# Function to find the intersection of two arrays
def find_intersection(arr1, arr2):
set1 = set(arr1)
# Removing duplicates from the first array
result = []
# Avoiding duplicates and adding intersections
for num in arr2:
if num in set1:
result.append(num)
set1.remove(num)
return result
# Driver code
if __name__ == "__main__":
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
# Function call
intersection = find_intersection(arr1, arr2)
for num in intersection:
print(num, end=" ")
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the intersection of two arrays
static List<int> Intersection(int[] arr1, int[] arr2)
{
// Create a HashSet to store unique elements from
// the first array
HashSet<int> set = new HashSet<int>(arr1);
// Create a list to store the intersection elements
List<int> result = new List<int>();
// Iterate through the second array
foreach (int num in arr2)
{
// If the element is in the HashSet
// it's an intersection element
if (set.Contains(num))
{
result.Add(num);
// Remove the element from the HashSet to
// avoid duplicates
set.Remove(num);
}
}
return result;
}
static void Main()
{
int[] arr1 = { 1, 2, 4, 5, 6 };
int[] arr2 = { 2, 3, 5, 7 };
// Function call
List<int> intersection = Intersection(arr1, arr2);
// Print the intersection elements
foreach (int num in intersection)
{
Console.Write(num + " ");
}
Console.WriteLine();
}
}
// Function to find the intersection of two arrays
function find_intersection(arr1, arr2) {
const set1 = new Set(arr1);
// Initialize an empty array to store the intersection elements
const result = [];
// Iterate through the second array to find intersections
for (const num of arr2) {
if (set1.has(num)) {
result.push(num);
set1.delete(num);
}
}
return result;
}
// Driver code
if (true) { // JavaScript doesn't have an exact equivalent to "__name__ == '__main__'"
const arr1 = [1, 2, 4, 5, 6];
const arr2 = [2, 3, 5, 7];
// Function call
const intersection = find_intersection(arr1, arr2);
// Print the intersection elements
for (const num of intersection) {
console.log(num + " ");
}
}
Output
2 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)