Saturday, December 28, 2024
Google search engine
HomeData Modelling & AIUnion and Intersection of two sorted arrays

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}

We strongly recommend that you click here and practice it, before moving on to the solution.

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++




// 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




// 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


Python3




# 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=" ")


C#




// 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.


Javascript




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)

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++




// 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




// 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


Python3




# 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#




// 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.


Javascript




// 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 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++




// 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




// 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




// 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);
    }
}


Python3




# 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#




// 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


Javascript




<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
// 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 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++




// This implementation uses vectors but can be easily modified to adapt arrays
#include <bits/stdc++.h>
using namespace std;
 
/* Helper function for printUnion().
   This same function can also be implemented as a lambda function inside printUnion().
*/
void next_distinct(const vector<int> &arr, int &x) // Moving to next distinct element
{
  // vector CAN be passed by reference to avoid unnecessary copies.
  // x(index) MUST be passed by reference so to reflect the change in the original index parameter
   
  /* Checks whether the previous element is equal to the current element,
       if true move to the element at the next index else return with the current index
  */
    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); // Incrementing i to next distinct element
        }
        else if (arr1[i] > arr2[j])
        {
            cout << arr2[j] << " ";
            next_distinct(arr2, j); // Incrementing j to next distinct element
        }
        else
        {
            cout << arr1[i] << " ";
            // OR cout << arr2[j] << " ";
            next_distinct(arr1, i); // Incrementing i to next distinct element
            next_distinct(arr2, j); // Incrementing j to next distinct element
        }
    }
    // Remaining elements of the larger array
    while (i < arr1.size())
    {
        cout << arr1[i] << " ";
        next_distinct(arr1, i); // Incrementing i to next distinct element
    }
    while (j < arr2.size())
    {
        cout << arr2[j] << " ";
        next_distinct(arr2, j); // Incrementing j to next distinct element
    }
}
 
int main()
{
    vector<int> arr1 = {1, 2, 2, 2, 3};    // Duplicates Present
    vector<int> arr2 = {2, 3, 3, 4, 5, 5}; // Duplicates Present
 
    printUnion(arr1, arr2);
 
    return 0;
}
// This code is contributed by ciphersaini.


C




#include <stdio.h>
 
void next_distinct(int arr[], int size, int* x)
{
    /* Moving to next distinct element */
    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); // Incrementing i to next
                               // distinct element
        }
        else if (arr1[i] > arr2[j]) {
            printf("%d ", arr2[j]);
            next_distinct(arr2, size2,
                          &j); // Incrementing j to next
                               // distinct element
        }
        else {
            printf("%d ",
                   arr1[i]); // OR printf("%d ", arr2[j]);
            next_distinct(arr1, size1,
                          &i); // Incrementing i to next
                               // distinct element
            next_distinct(arr2, size2,
                          &j); // Incrementing j to next
                               // distinct element
        }
    }
    // Remaining elements of the larger array
    while (i < size1) {
        printf("%d ", arr1[i]);
        next_distinct(
            arr1, size1,
            &i); // Incrementing i to next distinct element
    }
    while (j < size2) {
        printf("%d ", arr2[j]);
        next_distinct(
            arr2, size2,
            &j); // Incrementing j to next distinct element
    }
}
 
int main()
{
    int arr1[] = { 1, 2, 2, 2, 3 }; // Duplicates Present
    int arr2[] = { 2, 3, 3, 4, 5, 5 }; // Duplicates Present
    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) {
        /*
        Helper function for printUnion(). This same function can also be implemented as a lambda function inside printUnion().
        This function moves to the next distinct element in the array.
        */
        while (x < arr.length - 1 && arr[x] == arr[x + 1]) {
            x++;
        }
        return x + 1;
    }
     
    public static void printUnion(int[] arr1, int[] arr2) {
        /*
        This function prints the union of two arrays without duplicates.
        */
        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):
    """
    Helper function for printUnion(). This same function can also be implemented as a lambda function inside printUnion().
    This function moves to the next distinct element in the array.
    """
    while x < len(arr) - 1 and arr[x] == arr[x + 1]:
        x += 1
    return x + 1
 
 
def printUnion(arr1, arr2):
    """
    This function prints the union of two arrays without duplicates.
 
    """
    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
{
    // Helper function for printUnion()
    // This same function can also be implemented as a lambda function inside printUnion()
    static void NextDistinct(List<int> arr, ref int x)
    {
        // List CAN be passed by reference to avoid unnecessary copies.
        // x(index) MUST be passed by reference so to reflect the change in the original index parameter
 
        // Checks whether the previous element is equal to the current element,
        // if true move to the element at the next index else return with the current index
        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); // Incrementing i to next distinct element
            }
            else if (arr1[i] > arr2[j])
            {
                Console.Write(arr2[j] + " ");
                NextDistinct(arr2, ref j); // Incrementing j to next distinct element
            }
            else
            {
                Console.Write(arr1[i] + " ");
                // OR Console.Write(arr2[j] + " ");
                NextDistinct(arr1, ref i); // Incrementing i to next distinct element
                NextDistinct(arr2, ref j); // Incrementing j to next distinct element
            }
        }
        // Remaining elements of the larger array
        while (i < arr1.Count)
        {
            Console.Write(arr1[i] + " ");
            NextDistinct(arr1, ref i); // Incrementing i to next distinct element
        }
        while (j < arr2.Count)
        {
            Console.Write(arr2[j] + " ");
            NextDistinct(arr2, ref j); // Incrementing j to next distinct element
        }
    }
 
    static void Main(string[] args)
    {
        List<int> arr1 = new List<int> { 1, 2, 2, 2, 3 }; // Duplicates Present
        List<int> arr2 = new List<int> { 2, 3, 3, 4, 5, 5 }; // Duplicates Present
 
        PrintUnion(arr1, arr2);
    }
}
//This code is contributed by Akash Jha


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];    // Duplicates Present
const arr2 = [2, 3, 3, 4, 5, 5]; // Duplicates Present
 
printUnion(arr1, arr2);
 
//This code is contributed by Akash Jha


Output

1 2 3 4 5 




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;
 
// 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;
}


Java




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 + " ");
        }
    }
}


Python3




# 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=" ")


C#




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();
    }
}


Javascript




// 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 + " ");
    }
}


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++




// C++ program to find intersection of
// two sorted arrays
#include <bits/stdc++.h>
using namespace std;
 
/* Function prints Intersection of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
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 /* if arr1[i] == arr2[j] */
        {
            cout << arr2[j] << " ";
            i++;
            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
    printIntersection(arr1, arr2, m, n);
 
    return 0;
}


C




// C program to find intersection of
// two sorted arrays
#include <stdio.h>
 
/* Function prints Intersection of arr1[] and arr2[]
   m is the number of elements in arr1[]
   n is the number of elements in arr2[] */
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 /* if arr1[i] == arr2[j] */
        {
            printf(" %d ", arr2[j++]);
            i++;
        }
    }
}
 
/* 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]);
    printIntersection(arr1, arr2, m, n);
    getchar();
    return 0;
}


Java




// Java program to find intersection of
// two sorted arrays
import java.io.*;
class FindIntersection {
    /* Function prints Intersection of arr1[] and arr2[]
       m is the number of elements in arr1[]
       n is the number of elements in arr2[] */
    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




# Python program to find intersection of
# two sorted arrays
# Function prints Intersection of arr1[] and arr2[]
# m is the number of elements in arr1[]
# n is the number of elements in arr2[]
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
 
# Driver program to test above function
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
m = len(arr1)
n = len(arr2)
printIntersection(arr1, arr2, m, n)
 
# This code is contributed by Pratik Chhajer


C#




// C# program to find Intersection of
// two sorted arrays
 
using System;
 
class GFG {
 
    /* Function prints Intersection of arr1[]
    and arr2[] m is the number of elements in arr1[]
    n is the number of elements in arr2[] */
    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++;
            }
        }
    }
 
    // driver code
    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);
    }
}
 
// This code is contributed by Sam007


Javascript




<script>
 
// JavaScript program to find intersection of
// two sorted arrays
 
// Function prints Intersection of arr1[] and arr2[]
// m is the number of elements in arr1[]
// n is the number of elements in arr2[]
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++;
        }
    }
}
 
// Driver code
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);
 
// This code is contributed by shivanisinghss2110
 
</script>


PHP




<?php
// PHP program to find intersection of
// two sorted arrays
 
/* Function prints Intersection
   of arr1[] and arr2[] m is the
   number of elements in arr1[]
   n is the number of elements
   in arr2[] */
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++;
             
        /* if arr1[i] == arr2[j] */
        else
        {
            echo $arr2[$j], " ";
            $i++;
            $j++;
        }
    }
}
 
// Driver Code
$arr1 = array(1, 2, 4, 5, 6);
$arr2 = array(2, 3, 5, 7);
 
$m = count($arr1);
$n = count($arr2);
 
// Function calling
printIntersection($arr1, $arr2, $m, $n);
 
// This code is contributed by anuj_67.
?>


Output

2 5 




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++




// C++ program to find intersection of
// two sorted arrays
#include <bits/stdc++.h>
using namespace std;
 
/* Function prints Intersection of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
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]) {        //For Handling duplicates
            i++;
            continue;
        }
        if (arr1[i] < arr2[j])
            i++;
        else if (arr2[j] < arr1[i])
            j++;
        else /* if arr1[i] == arr2[j] */
        {
            cout << arr2[j] << " ";
            i++;
            j++;
        }
    }
}
 
/* Driver program to test above function */
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]);
 
    // Function calling
    printIntersection(arr1, arr2, m, n);
 
    return 0;
}


C




// C program to find intersection of
// two sorted arrays
#include <stdio.h>
 
/* Function prints Intersection of arr1[] and arr2[]
   m is the number of elements in arr1[]
   n is the number of elements in arr2[] */
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]) {   //For Handling duplicates
            i++;
            continue;
        }
        if (arr1[i] < arr2[j])
            i++;
        else if (arr2[j] < arr1[i])
            j++;
        else /* if arr1[i] == arr2[j] */
        {
            printf(" %d ", arr2[j++]);
            i++;
        }
    }
}
 
/* Driver program to test above function */
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




// Java program to find intersection of
// two sorted arrays
import java.io.*;
class FindIntersection {
    /* Function prints Intersection of arr1[] and arr2[]
       m is the number of elements in arr1[]
       n is the number of elements in arr2[] */
    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]) {// For Handling duplicates
                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




# Python program to find intersection of
# two sorted arrays
 
# function prints intersection of arr1[] and arr2[]
# m is the number of elements in arr1[]
# n is the number of elements in arr2[]
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]): # For Handling duplicates
            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
 
 
# driver program
arr1 = [1,2,2,3,4]
arr2 = [2,2,4,6,7,8]
 
m = len(arr1)
n = len(arr2)
 
# function calling
printIntersection(arr1, arr2, m, n)
 
# This code is contributed by Kirti Agarwal(kirtiagarwal23121999)


C#




using System;
 
class Program
{
    /* Function prints Intersection of arr1[] and arr2[]
     * m is the number of elements in arr1[]
     * n is the number of elements in arr2[] */
    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])  //For Handling duplicates
            {
                i++;
                continue;
            }
            if (arr1[i] < arr2[j])
            {
                i++;
            }
            else if (arr2[j] < arr1[i])
            {
                j++;
            }
            else  //if arr1[i] == arr2[j]
            {
                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;
 
        // Function calling
        PrintIntersection(arr1, arr2, m, n);
 
        Console.ReadKey();
    }
}


Javascript




// JavaScript program to find intersection of
// two sorted arrays
 
/* Function prints Intersection of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
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 /* if arr1[i] == arr2[j] */
        {
            console.log(arr2[j] + " ")
            i++;
            j++;
        }
    }
}
 
// driver program
let arr1 = [1, 2, 2, 3, 4];
let arr2 = [2, 2, 4, 6, 7, 8];
 
let m = arr1.length;
let n = arr2.length;
 
// function calling
printIntersection(arr1, arr2, m, n);
 
// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002)


Output

2 4 




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. 

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

RELATED ARTICLES

Most Popular

Recent Comments