6.Union and Intersection of sorted arrays.

6.Union and Intersection of sorted arrays.

Problem link :- click here
This problem is similar to second part of the merge sort(you have to make some changes). Merge sort video is placed at the bottom.

C code

//Union and Intersection
#include<stdio.h>

void print_union(int A[], int B[], int m, int n)
{
     int i, j;
     i=0;
     j=0;

     while(i<m && j<n)
     {
         if(A[i] < B[j])
         {
             printf("\t%d",A[i]);
             i++;
         }
         else if(B[j] < A[i])
         {
              printf("\t%d",B[j]);
              j++;
         }
         else if(A[i] == B[j])
         {
             printf("\t%d",A[i]);
             i++;
             j++;
         }
     }

     while(i<m)
     {
          printf("\t%d",A[i]);
          i++;
     }
     while(j<n)
     {
         printf("\t%d",B[j]);
         j++;
     }
}

void print_intersection(int A[], int B[], int m, int n)
{
    int i, j;
    i=0;
    j=0;

    while(i<m && j<n)
     {
         if(A[i] < B[j])
             i++;
         else if(B[j] < A[i])
              j++;
         else if(A[i] == B[j])
         {
             printf("\t%d",A[i]);
             i++;
             j++;
         }
     }
}

void main()
{
    int arr1[30], arr2[30];
    int m, n;
    int i;

    printf("Enter the size of the array 1\n");
    scanf("%d",&m);
    printf("Enter the elements of array 1\n");
    for(i=0; i<m; i++)
        scanf("%d",&arr1[i]);
    printf("Enter the size of the array 2\n");
    scanf("%d",&n);
    printf("Enter the elements of array 2\n");
    for(i=0; i<n; i++)
        scanf("%d",&arr2[i]);

    printf("\nArray 1\n");
    for(i=0; i<m; i++)
        printf("\t%d",arr1[i]);
    printf("\n");
    printf("\nArray 2\n");
    for(i=0; i<n; i++)
        printf("\t%d",arr2[i]);
    printf("\n");

    printf("\n\nUnion of Array 1 and Array 2\n");
    print_union(arr1, arr2, m, n);

    printf("\n\nIntersection of Array 1 and Array 2\n");
    print_intersection(arr1, arr2, m, n);
    printf("\n\n");
}

Java code

//Union and Intersection
package programs;

import java.util.*;

public class Array__6
{

	static void print_union(int a[], int b[], int m, int n)
	{
		int i, j;
		i = 0;
		j = 0;
		while(i<m  &&  j<n)
		{
			if(a[i] < b[j])
			{
				System.out.print( a[i] + " ");
				i++;
			}
			else if(a[i] > b[j])
			{
				System.out.print( b[j] + " ");
				j++;
			}
			else if(a[i] == b[j])
			{
				System.out.print( a[i] + " ");
				i++;
				j++;
			}
		}
		while(i<m)
		{
			System.out.print( a[i] + " ");
			i++;
		}
		while(j<n)
		{
			System.out.print( b[j] + " ");
			j++;
		}
	}
	
	static void print_intersect(int a[], int b[], int m, int n)
	{
		int i, j;
		i = 0;
		j = 0;
		while(i<m  &&  j<n)
		{
			if(a[i] < b[j])
				i++;
			else if(a[i] > b[j])
				j++;
			else if(a[i] == b[j])
			{
				System.out.print(a[i] + " ");
				i++;
				j++;
			}
		}
	}
	
	public static void main(String[] args)
	{
		int array1[] = new int[20];
		int array2[] = new int[20];
		int m, n, i;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array 1 :");
		m = s.nextInt();
		System.out.println("Enter the elements of the array 1 :");
		for(i=0; i<m; i++)
			array1[i] = s.nextInt();
		System.out.print("Enter the size of the array 2 :");
		n = s.nextInt();
		System.out.println("Enter the elements of the array 2 :");
		for(i=0; i<n; i++)
			array2[i] = s.nextInt();
		
		System.out.println("Array 1 :");
		print_array(array1, n);
		System.out.println("\nArray 2 :");
		print_array(array2, n);
		
		System.out.println("\n\nUnion of two arrays is :");
		print_union(array1, array2, m, n);
		System.out.println("\n\nIntersection of two arrays is :");
		print_intersect(array1, array2, m, n);

	}

	static void print_array(int arr[], int n)
	{
		for(int i=0; i<n; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O((n+m)log(n+m))
Space complexity :- O(n+m)