Find Intersection Between 2 Arrays

Find Intersection Between 2 Arrays

Example:1
Array-1 -- {1,2,3,10,20,5,8}
Array-1 --{20,1,90,30}

Output: 1,20

Example:2
Array-1 -- {10,20,10,10,50,80}
Array-1 --{10,10,10,10}

Output: 10

Steps & Complexity
Step:1 Sort any array[eg:Array-2]
Step:2 Take each element from an array:1, do a binary search for each element in array-1 with Array2
Step:3 If found- add into the set
Step:4 Else increment

Complexity : O(nlogn)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

import java.util.Arrays; import java.util.HashSet; import java.util.Set; public class IntersectionOfArrays { public static void main(String[] args) { IntersectionOfArrays obj= new IntersectionOfArrays(); int arr1[]= {1,3,5,10,2,10,10,10,10,22}; int arr2[]= {10,10,10,10,10,10}; int[] resul = obj.intersection(arr1, arr2); System.out.println(Arrays.toString(resul)); } public int[] intersection(int[] arr1, int[] arr2) { Set<Integer> set = new HashSet<>(); Arrays.sort(arr2); for (Integer nums : arr1) { if (binarySearch(arr2, nums)) { set.add(nums); } } int[] result = new int[set.size()]; int i = 0; for (Integer num : set) { result[i++] = num; } return result; } public boolean binarySearch(int[] arr, int target) { int low = 0; int high = arr.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { return true; } if (arr[mid] > target) { high = mid - 1; } else { low = mid + 1; } } return false; } }