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++ program to find union of
// two sorted arrays
#include <bits/stdc++.h>
using namespace std;
/* Function prints union of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
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++;
}
}
/* Print remaining elements of the larger array */
while (i < m)
cout << arr1[i++] << " ";
while (j < n)
cout << arr2[j++] << " ";
}
/* Driver program to test above function */
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]);
// Function calling
printUnion(arr1, arr2, m, n);
return 0;
}
// C program to find union of
// two sorted arrays
#include <stdio.h>
/* Function prints union of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
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++;
}
}
/* Print remaining elements of the larger array */
while (i < m)
printf(" %d ", arr1[i++]);
while (j < n)
printf(" %d ", arr2[j++]);
}
/* Driver program to test above function */
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 program to find union of
// two sorted arrays
import java.io.*;
class FindUnion {
/* Function prints union of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
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++;
}
}
/* Print remaining elements of
the larger array */
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);
}
}
# Python program to find union of
# two sorted arrays
# Function prints union of arr1[] and arr2[]
# m is the number of elements in arr1[]
# n is the number of elements in arr2[]
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
# Print remaining elements of the larger array
while i < m:
print(arr1[i],end=" ")
i += 1
while j < n:
print(arr2[j],end=" ")
j += 1
# Driver program to test above function
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
m = len(arr1)
n = len(arr2)
printUnion(arr1, arr2, m, n)
# This code is contributed by Pratik Chhajer
// C# program to find union of
// two sorted arrays
using System;
class GFG {
/* Function prints union of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
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++;
}
}
/* Print remaining elements of
the larger array */
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);
}
}
// This code is contributed by Sam007
<script>
// JavaScript program to find union of
// two sorted arrays
/* Function prints union of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
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++;
}
}
/* Print remaining elements of
the larger array */
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);
// this code is contributed by shivanisinghss2110
</script>
<?php
// PHP program to find union of
// two sorted arrays
/* Function prints union of
arr1[] and arr2[] m is the
number of elements in arr1[]
n is the number of elements
in arr2[] */
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++;
}
}
// Print remaining elements
// of the larger array
while($i < $m)
echo($arr1[$i++] . " ");
while($j < $n)
echo($arr2[$j++] . " ");
}
// Driver Code
$arr1 = array(1, 2, 4, 5, 6);
$arr2 = array(2, 3, 5, 7);
$m = sizeof($arr1);
$n = sizeof($arr2);
// Function calling
printUnion($arr1, $arr2, $m, $n);
// This code is contributed by Ajit.
?>
Output
1 2 3 4 5 6 7
Time Complexity : O(m + n)
Auxiliary Space: O(1)
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)