DEV Community

loading...
Cover image for 🔰Union & Intersection of two sorted arrays🔰

🔰Union & Intersection of two sorted arrays🔰

Kaiwalya Koparkar
Front-end Developer @Codemugg|🌐 Open Source Enthusiast | 💻 Full Stack Developer | 📎Blogger 📜| Competitive Programmer | Man who Dreams In Code 💻
・3 min read

Question:

Given two arrays A and B of size N and M respectively. The task is to find union between these two arrays.

Union of the two arrays can be defined as the set containing distinct elements from both the arrays. If there are repetitions, then only one occurrence of element should be printed in union.

Example 1:

Input:
5 3
1 2 3 4 5
1 2 3

Output: 
5

Explanation: 
1, 2, 3, 4 and 5 are the
elements which comes in the union set
of both arrays. So count is 5.
Enter fullscreen mode Exit fullscreen mode

Logic:

  1. Sets data structure ( Library function )
    • take the input as two arrays
    • create 2 sets a1 containing 1st array, b1 containing 2nd array
    • printing a1. addAll ( b1 ) will show the union of the set
    • to find an intersection we have to find if all the elements in the small set are present in a large set for that we will use largeSet. contains ( small ).
    • Print the intersection of the set
  2. Compare and insert
    • we will make two array list intersection and union.
    • create visited array of size same as the small array among the a and b
    • if an element in the small array is present in the large array we will mark its location as visited [ i ] = 1;
    • add all the elements of the large array to union ArrayList
    • then iterate through visited. and find if visited [ i ] = 1 if it is 1 then add it to intersection arraylist and if visited [ i ] = 0 then add to union arraylist
import java.util.*;

public class Solution{
    public static void compareInsert(int a[], int b[], int n, int m){
        ArrayList<Integer> intersection = new ArrayList<>();
        ArrayList<Integer> union = new ArrayList<>();
        if(a.length > b.length){
            int visited[] = new int[m];
            for(int i = 0; i < b.length; i++){
                for(int j = 0; j < a.length; j++){
                    if(a[j] == b[i]){
                        visited[i] = 1;
                        break;
                    }
                }
            }
            for(int i = 0; i < visited.length; i++){
                if(visited[i] == 1){
                    intersection.add(b[i]);
                }
            }
            for(int i = 0; i < a.length ; i++){
                union.add(a[i]);
            }
            for(int i = 0; i < visited.length; i++){
                if(visited[i] == 0){
                    union.add(b[i]);
                }
            }

            System.out.println("Intersection through compare and insert is: "+intersection);
            System.out.println("Union through compare and insert is: "+union);

        }else if(b.length > a.length){
            int visited[] = new int[n];
            for(int i = 0; i < a.length; i++){
                for(int j = 0; j < b.length; j++){
                    if(a[i] == b[j]){
                        visited[i] = 1;
                        break;
                    }
                }
            }

            for(int i = 0; i < visited.length; i++){
                if(visited[i] == 1){
                    intersection.add(a[i]);
                }
            }
            for(int i = 0; i < b.length; i++){
                union.add(b[i]);
            }
            for(int i = 0; i < visited.length; i++){
                if(visited[i] == 0){
                    union.add(a[i]);
                }
            }

            System.out.println("Intersection through compare and insert is: "+intersection);
            System.out.println("Union through compare and insert is: "+union);

        }
    }
    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];
        int b[] = new int[m];

        for(int i=0; i<a.length; i++){
            a[i] = sc.nextInt();
        }
        for(int i=0; i<b.length; i++){
            b[i] = sc.nextInt();
        }

        //This is a inbuilt library solution
        Set<Integer> a1 = new HashSet<>();
        Set<Integer> b1 = new HashSet<>();

       for(int i = 0; i < a.length; i++){
            a1.add(a[i]);
        }
        for(int i = 0; i < b.length; i++){
            b1.add(b[i]);
        }

        if(a1.size() > b1.size()){
            if(a1.containsAll(b1) == true){
                System.out.println("Itersection of the set is: "+b1);
            }
        }else if(a1.size() < b1.size()){
             if(b1.containsAll(a1) == true){
                System.out.println("Itersection of the set is: "+a1);
            }
        }
        a1.addAll(b1);
        System.out.println("Union of the set is: "+a1);

        //This is compare and insert solution
        compareInsert(a,b,n,m);
    }
}
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

Forem Open with the Forem app