Union of Two Arrays

Problem Statement

Given two unsorted arrays that represent two sets (elements in every array are distinct), find the union and intersection of two arrays.

Example:

arr1[] = {7, 1, 5, 2, 3, 6}
arr2[] = {3, 8, 6, 20, 7}

Then your program should print the Union as {1, 2, 3, 5, 6, 7, 8, 20}.

Implementation

A simple approach is to put elements from both arrays into a single array, sort the combined array, and then extract the unique elements.

function printUnion(a, b, m, n) {
    let c = [];
    
    // Copy elements from the first array
    for (let i = 0; i < m; i++) {
        c[i] = a[i];
    }
        
    // Copy elements from the second array
    for (let i = 0; i < n; i++) {
        c[i + m] = b[i];
    }
        
    // Sort the combined array
    c.sort(function(a, b) {
        return a - b;
    });
    
    let union = [];
    let k = 0;
    
    // Traverse the sorted array to collect only unique elements
    for (let i = 0; i < m + n; i++) {
        // If it's the first element or not equal to the previous element
        if (i === 0 || c[i] !== c[i - 1]) {
            union[k++] = c[i];
        }
    }
    
    return union;
}
 
// Example usage:
let a = [3, 8, 10];
let b = [2, 8, 9, 10, 15];
 
let output = printUnion(a, b, a.length, b.length);
console.log(output);

Output:

[2, 3, 8, 9, 10, 15]

Complexity Analysis

Time Complexity: O((m+n) * log(m+n)) for the sorting approach shown above. Alternatively, the time complexity can be O(m * log(m) + n * log(n)) if using a map/set data structure depending on the implementation.
Auxiliary Space: O(m + n) to store the combined array c and the resulting union array.

Count Inversions Bit Manipulation