Union and Intersection of Two Sorted Arrays

Union and Intersection of Two Sorted arrays

Given two sorted arrays of any length, Find Union and Intersection of given arrays.

Lets understand the problem statement graphically and it will be more clear,

union and intersection of two arrays in java
Union and Intersection of two arrays in Java 

Algorithm


Take 2 pointers i and j,
  1. Pointer i pointing to 1st index of Array 1 & Pointer j pointing to 1st index of Array 2
  2. If arr1[i] == arr2[j], it means, element is common in both array, So write it to intersection string and one copy to union string as well and increment both pointer i and j.
  3. If arr1[i] < arr2[j], it means, arr[i] is smaller, So write arr1[i] to union string and increment pointer i.
  4. If arr1[i] > arr2[j], it means, arr[j] is smaller, So write arr2[j] to union string and increment pointer j.
  5. If the length of arr1 and arr2 is different, then comparison works till length of both array is same. So after comparison loop breaks, we need to check which array is larger and copy that array element to union string.
algorithm to find union and intersection of two sorted arrays
Algorithm to find union and intersection of two sorted arrays

Union and Intersection of Two Sorted arrays Java Program


package javabypatel;

public class UnionAndIntersectionOfTtwoSortedArrays {
 public static void main(String[] args) {
  int arr1[] = {10, 15, 22, 80};
  int arr2[] = {5, 10, 11, 22, 70, 90};
  
  unionAndIntersectionOfTtwoSortedArrays(arr1, arr2);
 }
 
 private static void unionAndIntersectionOfTtwoSortedArrays(int[] arr1, int[] arr2){
  String union = "";
  String intersection = "";
  
  int i=0; int j=0;
  while(i < arr1.length && j < arr2.length) {
   if(arr1[i] == arr2[j]){
    union += arr1[i] + " ";
    intersection += arr1[i] + " ";
    
    i++; j++;
   }else if(arr1[i] < arr2[j]){
    union += arr1[i] + " ";
    i++;
   }else{
    union += arr2[j] + " ";
    j++;
   }
  }
  
  while(i < arr1.length){
   union += arr1[i];
  }
   
  while(j < arr2.length) {
   union += arr2[j];
  }
  
  System.out.println("union :"+union);
  System.out.println("intersection :"+intersection);
 }
}

You may also like to see


Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

Advanced Multithreading Interview Questions-Answers In Java

Type Casting Interview Questions-Answers In Java

How Thread.join() in Java works internally

How is ambiguous overloaded method call resolved in java


Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment