Find Union of Two Arrays

Problem Statement

Given two arrays, find the union of the arrays.

The union of two arrays contains:

• All distinct elements
• Elements appearing only once, even if they exist in both arrays

The order of elements does not matter unless explicitly stated.

Example 1

Input

arr1 = [1, 2, 3, 4]
arr2 = [3, 4, 5, 6]

Output

[1, 2, 3, 4, 5, 6]

Example 2

Input

arr1 = [1, 1, 2, 2]
arr2 = [2, 3, 3]

Output

[1, 2, 3]

Why This Problem Is Important

• Frequently asked array interview question
• Tests understanding of:
  • Duplicate handling
  • Hashing
  • Sorting logic
• Used in:
  • Data processing
  • Set operations
  • Merging datasets

Approaches to Solve the Problem

1. Brute Force (Nested Loop)
2. Using Hashing (Most Efficient)
3. Using Sorting + Two Pointers (For Sorted Arrays)

Approach 1: Brute Force Method

Idea

1. Add all elements of the first array to a result array
2. For each element of the second array:
   • Check if it already exists in the result
   • Add only if not present

Algorithm

1. Create an empty result array
2. Insert all elements of arr1
3. For each element in arr2, check existence in result
4. Add element if not found

Time and Space Complexity

• Time Complexity: O(n * m)
• Space Complexity: O(n + m)

C Implementation

#include 

int main() {
    int arr1[] = {1, 2, 3, 4};
    int arr2[] = {3, 4, 5, 6};
    int n1 = 4, n2 = 4;
    int unionArr[10], k = 0;
    int found;

    for(int i = 0; i < n1; i++)
        unionArr[k++] = arr1[i];

    for(int i = 0; i < n2; i++) {
        found = 0;
        for(int j = 0; j < k; j++) {
            if(arr2[i] == unionArr[j]) {
                found = 1;
                break;
            }
        }
        if(!found)
            unionArr[k++] = arr2[i];
    }

    for(int i = 0; i < k; i++)
        printf("%d ", unionArr[i]);

    return 0;
}

Approach 2: Using Hashing (Recommended)

Idea

• Use a hash set to store unique elements
• Insert elements from both arrays
• Hashing automatically removes duplicates

Algorithm

1. Create a hash set
2. Insert all elements of arr1
3. Insert all elements of arr2
4. Print all elements from the set

Time and Space Complexity

• Time Complexity: O(n + m)
• Space Complexity: O(n + m)

C++ Implementation

#include 
#include 
using namespace std;

int main() {
    int arr1[] = {1, 2, 3, 4};
    int arr2[] = {3, 4, 5, 6};

    unordered_set s;

    for(int x : arr1) s.insert(x);
    for(int x : arr2) s.insert(x);

    for(int x : s)
        cout << x << " ";
}

Java Implementation

import java.util.*;

public class UnionArray {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4};
        int[] arr2 = {3, 4, 5, 6};

        Set set = new HashSet<>();

        for(int x : arr1) set.add(x);
        for(int x : arr2) set.add(x);

        System.out.println(set);
    }
}

Python Implementation

arr1 = [1, 2, 3, 4]
arr2 = [3, 4, 5, 6]

union = list(set(arr1) | set(arr2))
print(union)

JavaScript Implementation

let arr1 = [1, 2, 3, 4];
let arr2 = [3, 4, 5, 6];

let union = [...new Set([...arr1, ...arr2])];
console.log(union);

Approach 3: Sorting + Two Pointers (If Arrays Are Sorted)

Idea

• Sort both arrays
• Use two pointers to compare elements
• Skip duplicates while inserting

Time and Space Complexity

• Time Complexity: O(n log n + m log m)
• Space Complexity: O(n + m)

Dry Run (Hashing Approach)

arr1 = [1, 2, 3, 4]
arr2 = [3, 4, 5, 6]

Insert arr1 → {1, 2, 3, 4}
Insert arr2 → {1, 2, 3, 4, 5, 6}

Summary

• Union contains unique elements from both arrays
• Hashing is the best and fastest approach
• Brute force is useful for understanding logic
• Sorting approach works well for already sorted arrays

Key Points

• Time Complexity (Best): O(n + m)
• Space Complexity: O(n + m)
• Order is not guaranteed unless specified

Next Problem in the Series

Find Intersection of Two Arrays