Problem Statement: Given two sorted arrays, arr1, and arr2 of size n and m. Find the union of two sorted arrays.
The union of two arrays can be defined as the common and distinct elements in the two arrays.NOTE: Elements in the union should be in ascending order.
Examples
Example 1:
Input:
n = 5,m = 5.
arr1[] = {1,2,3,4,5}
arr2[] = {2,3,4,4,5}
Output:
{1,2,3,4,5}
Explanation:
Common Elements in arr1 and arr2 are: 2,3,4,5
Distnict Elements in arr1 are : 1
Distnict Elemennts in arr2 are : No distinct elements.
Union of arr1 and arr2 is {1,2,3,4,5}
Example 2:
Input:
n = 10,m = 7.
arr1[] = {1,2,3,4,5,6,7,8,9,10}
arr2[] = {2,3,4,4,5,11,12}
Output: {1,2,3,4,5,6,7,8,9,10,11,12}
Explanation:
Common Elements in arr1 and arr2 are: 2,3,4,5
Distnict Elements in arr1 are : 1,6,7,8,9,10
Distnict Elemennts in arr2 are : 11,12
Union of arr1 and arr2 is {1,2,3,4,5,6,7,8,9,10,11,12}
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:
Algorithm / Intuition
Solution 1: Using Map
Our aim is to find the common elements in arr1 and arr2, and the distinct elements of arr1,arr2. Use a Single map to find the frequencies of elements in arr1 and arr2.
As we are using only a single map the common element in arr1 and arr2 are treated as a single element for finding frequency, so there would be no duplicates.
Why not unordered_map?
In unordered_map the keys are stored in random order, while in the map the keys are stored in sorted order (ascending order by default). As we require elements of the union to be in ascending order, using a map is preferable.
We can also use unordered_map, but after finding the union of arr1 and arr2, we need to sort the union vector to get the elements of the union in sorted order.
Code
#include <bits/stdc++.h>
using namespace std;
vector < int > FindUnion(int arr1[], int arr2[], int n, int m) {
map < int, int > freq;
vector < int > Union;
for (int i = 0; i < n; i++)
freq[arr1[i]]++;
for (int i = 0; i < m; i++)
freq[arr2[i]]++;
for (auto & it: freq)
Union.push_back(it.first);
return Union;
}
int main() {
int n = 10, m = 7;
int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int arr2[] = {2, 3, 4, 4, 5, 11, 12};
vector < int > Union = FindUnion(arr1, arr2, n, m);
cout << "Union of arr1 and arr2 is " << endl;
for (auto & val: Union)
cout << val << " ";
return 0;
}
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
import java.util.*;
class TUF{
static ArrayList<Integer> FindUnion(int arr1[], int arr2[], int n, int m) {
HashMap <Integer,Integer > freq=new HashMap<>();
ArrayList<Integer> Union=new ArrayList<>();
for (int i = 0; i < n; i++)
freq.put(arr1[i],freq.getOrDefault(arr1[i],0)+1);
for (int i = 0; i < m; i++)
freq.put(arr2[i],freq.getOrDefault(arr2[i],0)+1);
for (int it: freq.keySet())
Union.add(it);
return Union;
}
public static void main(String args[]) {
int n = 10, m = 7;
int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int arr2[] = {2, 3, 4, 4, 5, 11, 12};
ArrayList<Integer> Union = FindUnion(arr1, arr2, n, m);
System.out.println("Union of arr1 and arr2 is ");
for (int val: Union)
System.out.print(val+" ");
}
}
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
def find_union(arr1, arr2):
freq = {}
union = []
for num in arr1:
freq[num] = freq.get(num, 0) + 1
for num in arr2:
freq[num] = freq.get(num, 0) + 1
for num in freq:
union.append(num)
return union
arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
arr2 = [2, 3, 4, 4, 5, 11, 12]
union = find_union(arr1, arr2)
print("Union of arr1 and arr2 is:")
for num in union:
print(num, end=" ")
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
function findUnion(arr1, arr2) {
let freq = new Map();
let union = [];
for (let num of arr1) {
freq.set(num, (freq.get(num) || 0) + 1);
}
for (let num of arr2) {
freq.set(num, (freq.get(num) || 0) + 1);
}
for (let [num, count] of freq) {
union.push(num);
}
return union;
}
let arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let arr2 = [2, 3, 4, 4, 5, 11, 12];
let union = findUnion(arr1, arr2);
console.log("Union of arr1 and arr2 is:");
console.log(union.join(" "));
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
Complexity Analysis
Time Compleixty : O( (m+n)log(m+n) ) . Inserting a key in map takes logN times, where N is no of elements in map. At max map can store m+n elements {when there are no common elements and elements in arr,arr2 are distntict}. So Inserting m+n th element takes log(m+n) time. Upon approximation across insertion of all elements in worst it would take O((m+n)log(m+n) time.
Using HashMap also takes the same time, On average insertion in unordered_map takes O(1) time but sorting the union vector takes O((m+n)log(m+n)) time. Because at max union vector can have m+n elements.
Space Complexity : O(m+n) {If Space of Union ArrayList is considered}
O(1) {If Space of union ArrayList is not considered}
Solution 2:
Algorithm / Intuition
Solution 2: Using Set
Suppose we consider arr1 and arr2 as a single array say arr, then the union of arr1 and arr2 is the distinct elements in arr.
Example:
arr1[] = {1,2,3,4,5,6,7,8,9,10}
arr2[] = {2,3,4,4,5,11,12}
arr = arr1 + arr2 = {1,2,3,4,5,67,8,9,
10,2,3,4,4,5,11,12}
Distinct element in
arr = {1,2,3,4,5,6,7,8,9,10,11,12}
= Union of arr1 ,arr2.
So using a set we can find the distinct elements because the set does not hold any duplicates. Hence we can find the union of arr1 and arr2.
Why not unordered_set?
In unordered_set the elements are stored in random order, while in a set the keys are stored in sorted order (ascending order by default). As we require elements of the union to be in ascending order, using a set is preferable.
We can also use unordered_set, but after finding the union of arr1 and arr2, we need to sort the union vector to get the elements of the union in sorted order.
Code
#include <bits/stdc++.h>
using namespace std;
vector < int > FindUnion(int arr1[], int arr2[], int n, int m) {
set < int > s;
vector < int > Union;
for (int i = 0; i < n; i++)
s.insert(arr1[i]);
for (int i = 0; i < m; i++)
s.insert(arr2[i]);
for (auto & it: s)
Union.push_back(it);
return Union;
}
int main()
{
int n = 10, m = 7;
int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int arr2[] = {2, 3, 4, 4, 5, 11, 12};
vector < int > Union = FindUnion(arr1, arr2, n, m);
cout << "Union of arr1 and arr2 is " << endl;
for (auto & val: Union)
cout << val << " ";
return 0;
}
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
import java.util.*;
class TUF{
static ArrayList<Integer> FindUnion(int arr1[], int arr2[], int n, int m) {
HashSet <Integer> s=new HashSet<>();
ArrayList < Integer > Union=new ArrayList<>();
for (int i = 0; i < n; i++)
s.add(arr1[i]);
for (int i = 0; i < m; i++)
s.add(arr2[i]);
for (int it: s)
Union.add(it);
return Union;
}
public static void main(String args[]) {
int n = 10, m = 7;
int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int arr2[] = {2, 3, 4, 4, 5, 11, 12};
ArrayList<Integer> Union = FindUnion(arr1, arr2, n, m);
System.out.println("Union of arr1 and arr2 is ");
for (int val: Union)
System.out.print(val+" ");
}
}
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
def find_union(arr1, arr2):
s = set()
union = []
for num in arr1:
s.add(num)
for num in arr2:
s.add(num)
for num in s:
union.append(num)
return union
arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
arr2 = [2, 3, 4, 4, 5, 11, 12]
union = find_union(arr1, arr2)
print("Union of arr1 and arr2 is:")
print(*union)
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
function findUnion(arr1, arr2) {
const set = new Set();
const union = [];
for (let num of arr1) {
set.add(num);
}
for (let num of arr2) {
set.add(num);
}
for (let num of set) {
union.push(num);
}
return union;
}
const arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const arr2 = [2, 3, 4, 4, 5, 11, 12];
const union = findUnion(arr1, arr2);
console.log("Union of arr1 and arr2 is:");
console.log(...union);
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
Complexity Analysis
Time Compleixty : O( (m+n)log(m+n) ) . Inserting an element in a set takes logN time, where N is no of elements in the set. At max set can store m+n elements {when there are no common elements and elements in arr,arr2 are distntict}. So Inserting m+n th element takes log(m+n) time. Upon approximation across inserting all elements in worst, it would take O((m+n)log(m+n) time.
Using HashSet also takes the same time, On average insertion in unordered_set takes O(1) time but sorting the union vector takes O((m+n)log(m+n)) time. Because at max union vector can have m+n elements.
Space Complexity : O(m+n) {If Space of Union ArrayList is considered}
O(1) {If Space of union ArrayList is not considered}
Solution 3:
Algorithm / Intuition
Solution 3: Two Pointers
Solution 1 and 2 work for the unsorted arrays also, The arrays arr1 and arr2 are sorted, can we use this property to reduce the time Complexity?
Using the property that the arrays are sorted we can bring down the time complexity from
O((m+n)log(m+n)) TO O(m+n).
Approach:
- Take two pointers let’s say i,j pointing to the 0th index of arr1 and arr2.
- Create an empty vector for storing the union of arr1 and arr2.
- From solution 2 we know that the union is nothing but the distinct elements in arr1 + arr2
- Let’s traverse the arr1 and arr2 using pointers i and j and insert the distinct elements found into the union vector.
While traversing we may encounter three cases.
- arr1[ i ] == arr2[ j ]
Here we found a common element, so insert only one element in the union. Let’s insert arr[i] in union and increment i.
NOTE: There may be cases like the element to be inserted is already present in the union, in that case, we are inserting duplicates which is not desired. So while inserting always check whether the last element in the union vector is equal or not to the element to be inserted. If equal we are trying to insert duplicates, so don’t insert the element, else insert the element in the union. This makes sure that we are not inserting any duplicates in the union because we are inserting elements in sorted order. - arr1[ i ] < arr2[ j ]
arr1[ i ] < arr2[ j ] so we need to insert arr1[ i ] in union.IF last element in union vector is not equal to arr1[ i ],then insert in union else don’t insert. After checking Increment i. - arr1[ i ] > arr2[ j ]
arr1[ i ] > arr2[ j ] so we need to insert arr2[ j ] in union. IF the last element in the union vector is not equal to arr2[ j ], then insert in the union, else don’t insert. After checking Increment j. After traversing if any elements are left in arr1 or arr2 check for condition and insert in the union.
Code
#include <bits/stdc++.h>
using namespace std;
vector < int > FindUnion(int arr1[], int arr2[], int n, int m) {
int i = 0, j = 0; // pointers
vector < int > Union; // Uninon vector
while (i < n && j < m) {
if (arr1[i] <= arr2[j]) // Case 1 and 2
{
if (Union.size() == 0 || Union.back() != arr1[i])
Union.push_back(arr1[i]);
i++;
} else // case 3
{
if (Union.size() == 0 || Union.back() != arr2[j])
Union.push_back(arr2[j]);
j++;
}
}
while (i < n) // IF any element left in arr1
{
if (Union.back() != arr1[i])
Union.push_back(arr1[i]);
i++;
}
while (j < m) // If any elements left in arr2
{
if (Union.back() != arr2[j])
Union.push_back(arr2[j]);
j++;
}
return Union;
}
int main()
{
int n = 10, m = 7;
int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int arr2[] = {2, 3, 4, 4, 5, 11, 12};
vector < int > Union = FindUnion(arr1, arr2, n, m);
cout << "Union of arr1 and arr2 is " << endl;
for (auto & val: Union)
cout << val << " ";
return 0;
}
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
import java.util.*;
class TUF{
static ArrayList<Integer> FindUnion(int arr1[], int arr2[], int n, int m) {
int i = 0, j = 0; // pointers
ArrayList<Integer > Union=new ArrayList<>(); // Uninon vector
while (i < n && j < m) {
if (arr1[i] <= arr2[j]) // Case 1 and 2
{
if (Union.size() == 0 || Union.get(Union.size()-1) != arr1[i])
Union.add(arr1[i]);
i++;
} else // case 3
{
if (Union.size() == 0 || Union.get(Union.size()-1) != arr2[j])
Union.add(arr2[j]);
j++;
}
}
while (i < n) // IF any element left in arr1
{
if (Union.get(Union.size()-1) != arr1[i])
Union.add(arr1[i]);
i++;
}
while (j < m) // If any elements left in arr2
{
if (Union.get(Union.size()-1) != arr2[j])
Union.add(arr2[j]);
j++;
}
return Union;
}
public static void main(String args[]) {
int n = 10, m = 7;
int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int arr2[] = {2, 3, 4, 4, 5, 11, 12};
ArrayList<Integer> Union = FindUnion(arr1, arr2, n, m);
System.out.println("Union of arr1 and arr2 is ");
for (int val: Union)
System.out.print(val+" ");
}
}
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
def find_union(arr1, arr2):
i, j = 0, 0 # Pointers
union = [] # Union list
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]: # Case 1 and 2
if len(union) == 0 or union[-1] != arr1[i]:
union.append(arr1[i])
i += 1
else: # Case 3
if len(union) == 0 or union[-1] != arr2[j]:
union.append(arr2[j])
j += 1
while i < len(arr1): # If any elements left in arr1
if union[-1] != arr1[i]:
union.append(arr1[i])
i += 1
while j < len(arr2): # If any elements left in arr2
if union[-1] != arr2[j]:
union.append(arr2[j])
j += 1
return union
arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
arr2 = [2, 3, 4, 4, 5, 11, 12]
union = find_union(arr1, arr2)
print("Union of arr1 and arr2 is:")
print(*union)
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
function findUnion(arr1, arr2) {
let i = 0, j = 0; // Pointers
let union = []; // Union array
while (i < arr1.length && j < arr2.length) {
if (arr1[i] <= arr2[j]) { // Case 1 and 2
if (union.length === 0 || union[union.length - 1] !== arr1[i])
union.push(arr1[i]);
i++;
} else { // Case 3
if (union.length === 0 || union[union.length - 1] !== arr2[j])
union.push(arr2[j]);
j++;
}
}
while (i < arr1.length) { // If any elements left in arr1
if (union[union.length - 1] !== arr1[i])
union.push(arr1[i]);
i++;
}
while (j < arr2.length) { // If any elements left in arr2
if (union[union.length - 1] !== arr2[j])
union.push(arr2[j]);
j++;
}
return union;
}
const arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const arr2 = [2, 3, 4, 4, 5, 11, 12];
const union = findUnion(arr1, arr2);
console.log("Union of arr1 and arr2 is:");
console.log(union.join(" "));
Output:
Union of arr1 and arr2 is
1 2 3 4 5 6 7 8 9 10 11 12.
Complexity Analysis
Time Complexity: O(m+n), Because at max i runs for n times and j runs for m times. When there are no common elements in arr1 and arr2 and all elements in arr1, arr2 are distinct.
Space Complexity : O(m+n) {If Space of Union ArrayList is considered}
O(1) {If Space of union ArrayList is not considered}
Video Explanation
Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article