Union and Intersection of two sorted arrays
Last Updated :
09 Oct, 2023
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++
#include <bits/stdc++.h>
using namespace std;
vector<int> Unionarray(int arr1[], int arr2[], int n, int m)
{
set<int> s;
for (int i = 0; i < n; i++) {
s.insert(arr1[i]);
}
for (int i = 0; i < m; i++) {
s.insert(arr2[i]);
}
vector<int> vec(s.begin(), s.end());
return vec;
}
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]);
vector<int> uni = Unionarray(arr1, arr2, n, m);
for (int i : uni) {
cout << i << " ";
}
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
public static ArrayList<Integer>
Unionarray(int arr1[], int arr2[],
int n, int m)
{
TreeSet<Integer> set = new TreeSet<>();
for (int i : arr1)
set.add(i);
for (int i : arr2)
set.add(i);
ArrayList<Integer> list
= new ArrayList<>();
for (int i : set)
list.add(i);
return list;
}
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;
ArrayList<Integer> uni
= Unionarray(arr1, arr2, n, m);
for (int i : uni) {
System.out.print(i + " ");
}
}
}
|
Python3
def Unionarray(arr1, arr2, n, m):
set1 = set(arr1)
set2 = set(arr2)
result = list(set1.union(set2))
return result
if __name__ == "__main__":
arr1 = [1, 2, 2, 2, 3]
arr2 = [2, 3, 3, 4, 5, 5]
n = len(arr1)
m = len(arr2)
uni = Unionarray(arr1, arr2, n, m)
for i in uni:
print(i, end=" ")
|
C#
using System;
using System.Collections.Generic;
public class GFG
{
public static List<int> Unionarray(int[] arr1, int[] arr2, int n, int m)
{
var set = new SortedSet<int>();
foreach (int i in arr1)
{ set.Add(i);
}
foreach (int i in arr2)
{ set.Add(i);
}
var list = new List<int>();
foreach (int i in set)
{ list.Add(i);
}
return list;
}
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;
var uni = GFG.Unionarray(arr1, arr2, n, m);
foreach (int i in uni)
{
Console.Write(i.ToString() + " ");
}
}
}
|
Javascript
function unionArray(arr1, arr2)
{
const set1 = new Set(arr1);
const set2 = new Set(arr2);
const result = [...new Set([...set1, ...set2])];
return result;
}
const arr1 = [1, 2, 2, 2, 3];
const arr2 = [2, 3, 3, 4, 5, 5];
const uni = unionArray(arr1, arr2);
console.log(uni.join(' '));
|
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 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++
#include <bits/stdc++.h>
using namespace std;
vector<int> Unionarray(int arr1[], int arr2[], int n, int m)
{
map<int, int> map;
for (int i = 0; i < n; i++)
{
if (map.find(arr1[i]) != map.end())
{
map[arr1[i]]++;
}
else
{
map[arr1[i]] = 1;
}
}
for (int i = 0; i < m; i++)
{
if (map.find(arr2[i]) != map.end())
{
map[arr2[i]]++;
}
else
{
map[arr2[i]] = 1;
}
}
vector<int> list;
for (auto i : map)
{
list.push_back(i.first);
}
return list;
}
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;
vector<int> uni = Unionarray(arr1, arr2, n, m);
for (auto i : uni)
{
cout << i << " ";
}
return 0;
}
|
Java
import java.io.*;
import java.util.*;
import java.util.HashMap;
class GFG {
public static ArrayList<Integer>
Unionarray(int arr1[], int arr2[],
int n, int m)
{
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
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);
}
}
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);
}
}
ArrayList<Integer> list = new ArrayList<>();
for (int i : map.keySet())
{
list.add(i);;
}
return list;
}
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 :");
ArrayList<Integer> uni
= Unionarray(arr1, arr2, n, m);
for (int i : uni) {
System.out.print(i + " ");
}
}
}
|
Python3
from typing import List
def Unionarray(arr1: List[int], arr2: List[int], n: int, m: int) -> List[int]:
map = {}
for i in range(n):
if arr1[i] in map:
map[arr1[i]] += 1
else:
map[arr1[i]] = 1
for i in range(m):
if arr2[i] in map:
map[arr2[i]] += 1
else:
map[arr2[i]] = 1
uni = list(map.keys())
return uni
arr1 = [1, 2, 2, 2, 3]
arr2 = [2, 3, 3, 4, 5, 5]
n = len(arr1)
m = len(arr2)
print("Union is :")
uni = Unionarray(arr1, arr2, n, m)
for i in uni:
print(i, end=" ")
|
C#
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>();
for (int i = 0; i < n; i++) {
if (map.ContainsKey(arr1[i])) {
map[arr1[i]] += 1;
}
else {
map.Add(arr1[i], 1);
}
}
for (int i = 0; i < m; i++) {
if (map.ContainsKey(arr2[i])) {
map[arr2[i]] += 1;
}
else {
map.Add(arr2[i], 1);
}
}
ArrayList list = new ArrayList();
foreach(int i in map.Keys) { list.Add(i); }
return list;
}
static public void Main()
{
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 :");
ArrayList uni = Unionarray(arr1, arr2, n, m);
foreach(int i in uni) { Console.Write(i + " "); }
}
}
|
Javascript
function Unionarray(arr1, arr2) {
let map = {};
for (let i = 0; i < arr1.length; i++) {
if (arr1[i] in map) {
map[arr1[i]] += 1;
} else {
map[arr1[i]] = 1;
}
}Q
for (let i = 0; i < arr2.length; i++) {
if (arr2[i] in map) {
map[arr2[i]] += 1;
} else {
map[arr2[i]] = 1;
}
}
let uni = Object.keys(map);
return uni;
}
let arr1 = [1, 2, 2, 2, 3];
let arr2 = [2, 3, 3, 4, 5, 5];
console.log("Union is :");
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 of Two-Sorted Arrays using Two-Pointers
To find union of two sorted arrays using two pointers, follow the following procedure :
- Use two index variables i and j, initial values i = 0, j = 0
- If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i.
- If arr1[i] is greater than arr2[j] then print arr2[j] and increment j.
- If both are same then print any of them and increment both i and j.
- Print remaining elements of the larger array.
Below is the implementation of the above approach :
C++
#include <bits/stdc++.h>
using namespace std;
void printUnion(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
cout << arr1[i++] << " ";
else if (arr2[j] < arr1[i])
cout << arr2[j++] << " ";
else {
cout << arr2[j++] << " ";
i++;
}
}
while (i < m)
cout << arr1[i++] << " ";
while (j < n)
cout << arr2[j++] << " ";
}
int main()
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
printUnion(arr1, arr2, m, n);
return 0;
}
|
C
#include <stdio.h>
void printUnion(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
printf(" %d ", arr1[i++]);
else if (arr2[j] < arr1[i])
printf(" %d ", arr2[j++]);
else {
printf(" %d ", arr2[j++]);
i++;
}
}
while (i < m)
printf(" %d ", arr1[i++]);
while (j < n)
printf(" %d ", arr2[j++]);
}
int main()
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
printUnion(arr1, arr2, m, n);
getchar();
return 0;
}
|
Java
import java.io.*;
class FindUnion {
static int printUnion(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
System.out.print(arr1[i++] + " ");
else if (arr2[j] < arr1[i])
System.out.print(arr2[j++] + " ");
else {
System.out.print(arr2[j++] + " ");
i++;
}
}
while (i < m)
System.out.print(arr1[i++] + " ");
while (j < n)
System.out.print(arr2[j++] + " ");
return 0;
}
public static void main(String args[])
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = arr1.length;
int n = arr2.length;
printUnion(arr1, arr2, m, n);
}
}
|
Python3
def printUnion(arr1, arr2, m, n):
i, j = 0, 0
while i < m and j < n:
if arr1[i] < arr2[j]:
print(arr1[i],end=" ")
i += 1
elif arr2[j] < arr1[i]:
print(arr2[j],end=" ")
j+= 1
else:
print(arr2[j],end=" ")
j += 1
i += 1
while i < m:
print(arr1[i],end=" ")
i += 1
while j < n:
print(arr2[j],end=" ")
j += 1
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
m = len(arr1)
n = len(arr2)
printUnion(arr1, arr2, m, n)
|
C#
using System;
class GFG {
static int printUnion(int[] arr1,
int[] arr2, int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
Console.Write(arr1[i++] + " ");
else if (arr2[j] < arr1[i])
Console.Write(arr2[j++] + " ");
else {
Console.Write(arr2[j++] + " ");
i++;
}
}
while (i < m)
Console.Write(arr1[i++] + " ");
while (j < n)
Console.Write(arr2[j++] + " ");
return 0;
}
public static void Main()
{
int[] arr1 = { 1, 2, 4, 5, 6 };
int[] arr2 = { 2, 3, 5, 7 };
int m = arr1.Length;
int n = arr2.Length;
printUnion(arr1, arr2, m, n);
}
}
|
Javascript
<script>
function printUnion( arr1, arr2, m, n)
{
var i = 0, 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;
}
var arr1 = [ 1, 2, 4, 5, 6 ];
var arr2 = [ 2, 3, 5, 7 ];
var m = arr1.length;
var n = arr2.length;
printUnion(arr1, arr2, m, n);
</script>
|
PHP
<?php
function printUnion($arr1, $arr2,
$m, $n)
{
$i = 0; $j = 0;
while ($i < $m && $j < $n)
{
if ($arr1[$i] < $arr2[$j])
echo($arr1[$i++] . " ");
else if ($arr2[$j] < $arr1[$i])
echo($arr2[$j++] . " ");
else
{
echo($arr2[$j++] . " ");
$i++;
}
}
while($i < $m)
echo($arr1[$i++] . " ");
while($j < $n)
echo($arr2[$j++] . " ");
}
$arr1 = array(1, 2, 4, 5, 6);
$arr2 = array(2, 3, 5, 7);
$m = sizeof($arr1);
$n = sizeof($arr2);
printUnion($arr1, $arr2, $m, $n);
?>
|
Time Complexity : O(m + n)
Auxiliary Space: O(1)
Union of Two-Sorted Arrays by Handling duplicates in any of the arrays:
Above code does not handle duplicates in any of the arrays. To handle the duplicates, check for every element whether adjacent elements are equal. This can be done by incrementing i or j such that i or j directly move to the next distinct element. This ensures the duplicate elements are not considered again. We can perform this operation in place (i.e. without using any extra space).
Below is the implementation of this approach.
C++
#include <bits/stdc++.h>
using namespace std;
void next_distinct(const vector<int> &arr, int &x)
{
do
{
++x;
} while (x < arr.size() && arr[x - 1] == arr[x]);
}
void printUnion(vector<int> arr1, vector<int> arr2)
{
int i = 0, j = 0;
while (i < arr1.size() && j < arr2.size())
{
if (arr1[i] < arr2[j])
{
cout << arr1[i] << " ";
next_distinct(arr1, i);
}
else if (arr1[i] > arr2[j])
{
cout << arr2[j] << " ";
next_distinct(arr2, j);
}
else
{
cout << arr1[i] << " ";
next_distinct(arr1, i);
next_distinct(arr2, j);
}
}
while (i < arr1.size())
{
cout << arr1[i] << " ";
next_distinct(arr1, i);
}
while (j < arr2.size())
{
cout << arr2[j] << " ";
next_distinct(arr2, j);
}
}
int main()
{
vector<int> arr1 = {1, 2, 2, 2, 3};
vector<int> arr2 = {2, 3, 3, 4, 5, 5};
printUnion(arr1, arr2);
return 0;
}
|
C
#include <stdio.h>
void next_distinct(int arr[], int size, int* x)
{
do {
++(*x);
} while (*x < size && arr[*x - 1] == arr[*x]);
}
void printUnion(int arr1[], int size1, int arr2[],
int size2)
{
int i = 0, j = 0;
while (i < size1 && j < size2) {
if (arr1[i] < arr2[j]) {
printf("%d ", arr1[i]);
next_distinct(arr1, size1,
&i);
}
else if (arr1[i] > arr2[j]) {
printf("%d ", arr2[j]);
next_distinct(arr2, size2,
&j);
}
else {
printf("%d ",
arr1[i]);
next_distinct(arr1, size1,
&i);
next_distinct(arr2, size2,
&j);
}
}
while (i < size1) {
printf("%d ", arr1[i]);
next_distinct(
arr1, size1,
&i);
}
while (j < size2) {
printf("%d ", arr2[j]);
next_distinct(
arr2, size2,
&j);
}
}
int main()
{
int arr1[] = { 1, 2, 2, 2, 3 };
int arr2[] = { 2, 3, 3, 4, 5, 5 };
int size1 = sizeof(arr1) / sizeof(arr1[0]);
int size2 = sizeof(arr2) / sizeof(arr2[0]);
printUnion(arr1, size1, arr2, size2);
return 0;
}
|
Java
public class GFG {
public static int nextDistinct(int[] arr, int x) {
while (x < arr.length - 1 && arr[x] == arr[x + 1]) {
x++;
}
return x + 1;
}
public static void printUnion(int[] arr1, int[] arr2) {
int i = 0;
int j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
System.out.print(arr1[i] + " ");
i = nextDistinct(arr1, i);
} else if (arr1[i] > arr2[j]) {
System.out.print(arr2[j] + " ");
j = nextDistinct(arr2, j);
} else {
System.out.print(arr1[i] + " ");
i = nextDistinct(arr1, i);
j = nextDistinct(arr2, j);
}
}
while (i < arr1.length) {
System.out.print(arr1[i] + " ");
i = nextDistinct(arr1, i);
}
while (j < arr2.length) {
System.out.print(arr2[j] + " ");
j = nextDistinct(arr2, j);
}
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 2, 2, 3};
int[] arr2 = {2, 3, 3, 4, 5, 5};
printUnion(arr1, arr2);
}
}
|
Python3
def next_distinct(arr, x):
while x < len(arr) - 1 and arr[x] == arr[x + 1]:
x += 1
return x + 1
def printUnion(arr1, arr2):
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
print(arr1[i], end=" ")
i = next_distinct(arr1, i)
elif arr1[i] > arr2[j]:
print(arr2[j], end=" ")
j = next_distinct(arr2, j)
else:
print(arr1[i], end=" ")
i = next_distinct(arr1, i)
j = next_distinct(arr2, j)
while i < len(arr1):
print(arr1[i], end=" ")
i = next_distinct(arr1, i)
while j < len(arr2):
print(arr2[j], end=" ")
j = next_distinct(arr2, j)
arr1 = [1, 2, 2, 2, 3]
arr2 = [2, 3, 3, 4, 5, 5]
printUnion(arr1, arr2)
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void NextDistinct(List<int> arr, ref int x)
{
do
{
++x;
} while (x < arr.Count && arr[x - 1] == arr[x]);
}
static void PrintUnion(List<int> arr1, List<int> arr2)
{
int i = 0, j = 0;
while (i < arr1.Count && j < arr2.Count)
{
if (arr1[i] < arr2[j])
{
Console.Write(arr1[i] + " ");
NextDistinct(arr1, ref i);
}
else if (arr1[i] > arr2[j])
{
Console.Write(arr2[j] + " ");
NextDistinct(arr2, ref j);
}
else
{
Console.Write(arr1[i] + " ");
NextDistinct(arr1, ref i);
NextDistinct(arr2, ref j);
}
}
while (i < arr1.Count)
{
Console.Write(arr1[i] + " ");
NextDistinct(arr1, ref i);
}
while (j < arr2.Count)
{
Console.Write(arr2[j] + " ");
NextDistinct(arr2, ref j);
}
}
static void Main(string[] args)
{
List<int> arr1 = new List<int> { 1, 2, 2, 2, 3 };
List<int> arr2 = new List<int> { 2, 3, 3, 4, 5, 5 };
PrintUnion(arr1, arr2);
}
}
|
Javascript
function nextDistinct(arr, x) {
do {
x++;
} while (x < arr.length && arr[x - 1] === arr[x]);
}
function printUnion(arr1, arr2) {
let i = 0, j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
console.log(arr1[i]);
nextDistinct(arr1, i);
} else if (arr1[i] > arr2[j]) {
console.log(arr2[j]);
nextDistinct(arr2, j);
} else {
console.log(arr1[i]);
nextDistinct(arr1, i);
nextDistinct(arr2, j);
}
}
while (i < arr1.length) {
console.log(arr1[i]);
nextDistinct(arr1, i);
}
while (j < arr2.length) {
console.log(arr2[j]);
nextDistinct(arr2, j);
}
}
const arr1 = [1, 2, 2, 2, 3];
const arr2 = [2, 3, 3, 4, 5, 5];
printUnion(arr1, arr2);
|
Time Complexity:O(m+n), where m & n are the sizes of the arrays.
Auxiliary Space: O(1)
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 :
C++
#include <bits/stdc++.h>
using namespace std;
vector<int> Intersection(int arr1[], int arr2[], int n,
int m)
{
set<int> st;
for (int i = 0; i < n; i++)
st.insert(arr1[i]);
vector<int> res;
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;
}
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]);
vector<int> inter = Intersection(arr1, arr2, n, m);
for (int i : inter)
cout << i << " ";
return 0;
}
|
Java
import java.util.HashSet;
import java.util.ArrayList;
public class Intersection {
public static ArrayList<Integer> findIntersection(int[] arr1, int[] arr2) {
HashSet<Integer> set = new HashSet<>();
for (int num : arr1) {
set.add(num);
}
ArrayList<Integer> result = new ArrayList<>();
for (int num : arr2) {
if (set.contains(num)) {
result.add(num);
set.remove(num);
}
}
return result;
}
public static void main(String[] args) {
int[] arr1 = { 1, 2, 4, 5, 6 };
int[] arr2 = { 2, 3, 5, 7 };
ArrayList<Integer> intersection = findIntersection(arr1, arr2);
for (int num : intersection) {
System.out.print(num + " ");
}
}
}
|
Python3
def find_intersection(arr1, arr2):
set1 = set(arr1)
result = []
for num in arr2:
if num in set1:
result.append(num)
set1.remove(num)
return result
if __name__ == "__main__":
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
intersection = find_intersection(arr1, arr2)
for num in intersection:
print(num, end=" ")
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static List<int> Intersection(int[] arr1, int[] arr2)
{
HashSet<int> set = new HashSet<int>(arr1);
List<int> result = new List<int>();
foreach (int num in arr2)
{
if (set.Contains(num))
{
result.Add(num);
set.Remove(num);
}
}
return result;
}
static void Main()
{
int[] arr1 = { 1, 2, 4, 5, 6 };
int[] arr2 = { 2, 3, 5, 7 };
List<int> intersection = Intersection(arr1, arr2);
foreach (int num in intersection)
{
Console.Write(num + " ");
}
Console.WriteLine();
}
}
|
Javascript
function find_intersection(arr1, arr2) {
const set1 = new Set(arr1);
const result = [];
for (const num of arr2) {
if (set1.has(num)) {
result.push(num);
set1.delete(num);
}
}
return result;
}
if (true) {
const arr1 = [1, 2, 4, 5, 6];
const arr2 = [2, 3, 5, 7];
const intersection = find_intersection(arr1, arr2);
for (const num of intersection) {
console.log(num + " ");
}
}
|
Time Complexity: O(m*log(m) + n*log(n)), where ‘m’ and ‘n’ are the size of the arrays
Auxiliary Space: O(m + n)
Intersection of Two-Sorted Arrays using Two-Pointers
To find intersection of two sorted arrays using two-pointers, follow the below approach :
- Use two index variables i and j, initial values i = 0, j = 0
- If arr1[i] is smaller than arr2[j] then increment i.
- If arr1[i] is greater than arr2[j] then increment j.
- If both are same then print any of them and increment both i and j.
Below is the implementation of the above approach :
C++
#include <bits/stdc++.h>
using namespace std;
void printIntersection(int arr1[], int arr2[], int m, int n)
{
int i = 0, 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()
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
printIntersection(arr1, arr2, m, n);
return 0;
}
|
C
#include <stdio.h>
void printIntersection(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
i++;
else if (arr2[j] < arr1[i])
j++;
else
{
printf(" %d ", arr2[j++]);
i++;
}
}
}
int main()
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
printIntersection(arr1, arr2, m, n);
getchar();
return 0;
}
|
Java
import java.io.*;
class FindIntersection {
static void printIntersection(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
i++;
else if (arr2[j] < arr1[i])
j++;
else {
System.out.print(arr2[j++] + " ");
i++;
}
}
}
public static void main(String args[])
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = arr1.length;
int n = arr2.length;
printIntersection(arr1, arr2, m, n);
}
}
|
Python3
def printIntersection(arr1, arr2, m, n):
i, j = 0, 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],end=" ")
j += 1
i += 1
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
m = len(arr1)
n = len(arr2)
printIntersection(arr1, arr2, m, n)
|
C#
using System;
class GFG {
static void printIntersection(int[] arr1,
int[] arr2, int m, int n)
{
int i = 0, 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++;
}
}
}
public static void Main()
{
int[] arr1 = { 1, 2, 4, 5, 6 };
int[] arr2 = { 2, 3, 5, 7 };
int m = arr1.Length;
int n = arr2.Length;
printIntersection(arr1, arr2, m, n);
}
}
|
Javascript
<script>
function printIntersection(arr1, arr2, m, n)
{
var i = 0, 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++;
}
}
}
var arr1 = [ 1, 2, 4, 5, 6 ];
var arr2 = [ 2, 3, 5, 7 ];
var m = arr1.length;
var n = arr2.length;
printIntersection(arr1, arr2, m, n);
</script>
|
PHP
<?php
function printIntersection($arr1, $arr2,
$m, $n)
{
$i = 0 ;
$j = 0;
while ($i < $m && $j < $n)
{
if ($arr1[$i] < $arr2[$j])
$i++;
else if ($arr2[$j] < $arr1[$i])
$j++;
else
{
echo $arr2[$j], " ";
$i++;
$j++;
}
}
}
$arr1 = array(1, 2, 4, 5, 6);
$arr2 = array(2, 3, 5, 7);
$m = count($arr1);
$n = count($arr2);
printIntersection($arr1, $arr2, $m, $n);
?>
|
Time Complexity : O(m + n)
Auxiliary Space: O(1)
Intersection of Two-Sorted Arrays by Handling duplicates in any of the arrays:
The above code does handles duplicate elements in arrays using set data structure . The intersection should not count duplicate elements. To handle this without set we can use an if statement to skip the iteration if previous element is same as current. Below is the algorithm of this approach.
- Use two index variables i and j, initial values i = 0, j = 0
- If index is greater than 0 and a[i]==a[i-1] then increment i.
- If arr1[i] is smaller than arr2[j] then increment i.
- If arr1[i] is greater than arr2[j] then increment j.
- If both are same then print any of them and increment both i and j.
Below is the implementation of the above approach :
C++
#include <bits/stdc++.h>
using namespace std;
void printIntersection(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (i > 0 && arr1[i] == arr1[i - 1]) {
i++;
continue;
}
if (arr1[i] < arr2[j])
i++;
else if (arr2[j] < arr1[i])
j++;
else
{
cout << arr2[j] << " ";
i++;
j++;
}
}
}
int main()
{
int arr1[] = { 1, 2, 2, 3, 4 };
int arr2[] = { 2, 2, 4, 6, 7, 8 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
printIntersection(arr1, arr2, m, n);
return 0;
}
|
C
#include <stdio.h>
void printIntersection(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (i > 0 && arr1[i] == arr1[i - 1]) {
i++;
continue;
}
if (arr1[i] < arr2[j])
i++;
else if (arr2[j] < arr1[i])
j++;
else
{
printf(" %d ", arr2[j++]);
i++;
}
}
}
int main()
{
int arr1[] = { 1, 2, 2, 3, 4 };
int arr2[] = { 2, 2, 4, 6, 7, 8 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
printIntersection(arr1, arr2, m, n);
getchar();
return 0;
}
|
Java
import java.io.*;
class FindIntersection {
static void printIntersection(int arr1[], int arr2[],
int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (i > 0
&& arr1[i] == arr1[i - 1]) {
i++;
continue;
}
if (arr1[i] < arr2[j])
i++;
else if (arr2[j] < arr1[i])
j++;
else {
System.out.print(arr2[j++] + " ");
i++;
}
}
}
public static void main(String args[])
{
int arr1[] = { 1, 2, 2, 3, 4 };
int arr2[] = { 2, 2, 4, 6, 7, 8 };
int m = arr1.length;
int n = arr2.length;
printIntersection(arr1, arr2, m, n);
}
}
|
Python3
def printIntersection(arr1, arr2, m, n):
i = 0
j = 0
while(i < m and j < n):
if(i > 0 and arr1[i] == arr1[i-1]):
i = i+1
continue
if(arr1[i] < arr2[j]):
i += 1
elif(arr2[j] < arr1[i]):
j += 1
else:
print(arr2[j], end=" ")
i+=1
j+=1
arr1 = [1,2,2,3,4]
arr2 = [2,2,4,6,7,8]
m = len(arr1)
n = len(arr2)
printIntersection(arr1, arr2, m, n)
|
C#
using System;
class Program
{
static void PrintIntersection(int[] arr1, int[] arr2, int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n)
{
if (i > 0 && arr1[i] == arr1[i - 1])
{
i++;
continue;
}
if (arr1[i] < arr2[j])
{
i++;
}
else if (arr2[j] < arr1[i])
{
j++;
}
else
{
Console.Write(arr2[j] + " ");
i++;
j++;
}
}
}
static void Main()
{
int[] arr1 = { 1, 2, 2, 3, 4 };
int[] arr2 = { 2, 2, 4, 6, 7, 8 };
int m = arr1.Length;
int n = arr2.Length;
PrintIntersection(arr1, arr2, m, n);
Console.ReadKey();
}
}
|
Javascript
function printIntersection(arr1, arr2, m, n){
let i = 0;
let j = 0;
while(i < m && j < n){
if(i > 0 && arr1[i] == arr1[i-1]){
i++;
continue;
}
if (arr1[i] < arr2[j])
i++;
else if (arr2[j] < arr1[i])
j++;
else
{
console.log(arr2[j] + " ")
i++;
j++;
}
}
}
let arr1 = [1, 2, 2, 3, 4];
let arr2 = [2, 2, 4, 6, 7, 8];
let m = arr1.length;
let n = arr2.length;
printIntersection(arr1, arr2, m, n);
|
Time Complexity : O(m + n)
Auxiliary Space: O(1)
See following post for unsorted arrays.
Find Union and Intersection of two unsorted arrays
Please write comments if you find any bug in above codes/algorithms, or find other ways to solve the same problem.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...