Use Sorting and Searching

Without using hashing or any predefined library like sets or maps and works even for both repeated and distant elements

Union:

Sort the smaller array, arr1, in ascending order.
Initialize an empty array ans to store the union.
Iterate through arr1 and add its elements to the ans array. For each element in arr2, check if it’s already in the ans array using binary search. If not found, add it to the ans array.

Intersection:

Determine the smaller array between arr1 and arr2. If arr1 is larger, swap them.
Sort the smaller array, arr1, in ascending order.
Initialize an empty array ans to store the intersection.
Iterate through arr1 and use binary search to check if each element exists in the larger array, arr2. If found in both arrays, add it to the ans array.

Example: This example describes the union & intersection of 2 unsorted Arrays by implementing Sorting and searching.

Javascript

function binarySearch(arr, l, r, x) { 
    if (r >= l) { 
        let mid = l + Math.floor((r - l) / 2); 
  
        // If the element is present 
        // at the middle itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, 
        // then it can only be present  
        // in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element 
    // is not present in array 
    return -1; 
} 
  
// Prints union of arr1 and arr2 
  
function printUnion(arr1, arr2, m, n) { 
  
    // Before finding union, make  
    // sure arr1 is smaller 
    if (m > n) { 
        let tempp = arr1; 
        arr1 = arr2; 
        arr2 = tempp; 
  
        let temp = m; 
        m = n; 
        n = temp; 
    } 
  
  
    let ans = []; 
    arr1.sort((a, b) => a - b); 
    for (let i = 0; i < m; i++) 
        ans.push(arr1[i]); 
  
    // Search every element of bigger 
    // array in smaller array 
    // and print the element if not found 
    for (let i = 0; i < n; i++) { 
        if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1) {  
            ans.push(arr2[i]);  
        } 
    } 
    console.log(ans) 
} 
  
// Prints intersection of arr1 and arr2 
  
function printIntersection(arr1, arr2, m, n) { 
  
    // Before finding intersection,  
    // make sure arr1[0..m-1] is smaller 
    if (m > n) { 
        let tempp = arr1; 
        arr1 = arr2; 
        arr2 = tempp; 
  
        let temp = m; 
        m = n; 
        n = temp; 
    } 
  
  
    arr1.sort((a, b) => a - b); 
  
    // Search every element of bigger array in smaller 
    // array and print the element if found 
    let ans = []; 
    for (let i = 0; i < n; i++) { 
        if (binarySearch(arr1, 0, m - 1, arr2[i]) != -1) { 
            ans.push(arr2[i]);  
           } 
    } 
    console.log(ans) 
} 
  
/* Driver program to test above function */
let arr1 = [7, 1, 5, 2, 3, 6]; 
let arr2 = [3, 8, 6, 20, 7]; 
let m = arr1.length; 
let n = arr2.length; 
  
// Function call 
console.log("Union of two arrays is"); 
printUnion(arr1, arr2, m, n); 
  
console.log("Intersection of two arrays is"); 
printIntersection(arr1, arr2, m, n);

Output

Union of two arrays is
[
   3, 6, 7, 8,
  20, 1, 5, 2
]
Intersection of two arrays is
[ 7, 3, 6 ]

Time Complexity: O(max(m*log(m), n*log(n)) + min(m, n) )

Auxiliary Space: O(1)

JavaScript Program to Find Union and Intersection of Two Unsorted Arrays

In this article, we will learn how to find the Union and Intersection of two arrays. When an array contains all the elements that are present in both of the arrays, it is called a union. On the other hand, if an array has only those elements that are common in both of the arrays, then it is called an intersection.

Example

Input: 
a = [1,3,5,7,9]  , b = [1,2,3,4,6,8,10]

Output: 
Union: [1,2,3,4,5,6,7,8,9,10]
Intersection: ans =[1,3]

Table of Content

Using Set
Using the map
Use Sorting
Use Sorting and Searching
Without using hashing or any predefined library like sets or maps and works even for both repeated and distant elements
Kind of hashing technique without using any predefined JavaScript Collections

We will understand the various approaches for finding the union and the intersection of two unsorted Arrays.

Tags:

#javascript-array #JavaScript-DSA #JavaScript-Program #JavaScript #Web Technologies

Use Sorting