Union of Two Arrays using Set - Optimal Approach

Visualization Player

Problem Statement

You are given two arrays arr1 and arr2. Your task is to return their union — a collection of all distinct elements that appear in either of the arrays.

The union should not contain any duplicate elements. The result can be returned in any order.

If both arrays are empty, return an empty array.

Examples

Array 1 Array 2 Union Result Description
[10, 20, 30] [30, 40, 50] [10, 20, 30, 40, 50] All unique elements from both arraysVisualization
[1, 1, 1] [1, 1, 1] [1] All elements are the same, so only one unique value in resultVisualization
[] [1, 2] [1, 2] One array is empty, return all elements of the non-empty arrayVisualization
[10, 20] [] [10, 20] One array is empty, return all elements of the non-empty arrayVisualization
[] [] [] Both arrays are empty, so result is also emptyVisualization
[5, 7, 9] [7, 5, 11] [5, 7, 9, 11] Duplicates across arrays removed in unionVisualization

Solution

Understanding the Problem: Union of Two Arrays

The goal is to compute the union of two arrays. That means we need to gather all the elements from both arrays, but include each element only once, even if it appears multiple times in either array.

For example, if the two arrays are:

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

The result should be [1, 2, 3, 4, 5] — note that 3 is not repeated.

Step-by-Step Approach

Step 1: Use a Set to Handle Uniqueness

A Set in most programming languages (like JavaScript, Python, Java) automatically keeps only unique values. This makes it perfect for solving union problems.

Step 2: Add All Elements from Both Arrays

Loop through each array, and add every element to the set. The set will automatically ignore duplicates.

Step 3: Convert the Set to a List (if needed)

Once all elements are added to the set, you can convert it back to an array or list to return the result.

Detailed Example for Beginners

Let’s consider:

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

1. Add from arr1:

  • Add 1 → set is {1}
  • Add 2 → set is {1, 2}
  • Add 3 → set is {1, 2, 3}
  • Add 2 again → set remains {1, 2, 3}

2. Add from arr2:

  • Add 2 → already in set
  • Add 3 → already in set
  • Add 4 → set is {1, 2, 3, 4}
  • Add 5 → set is {1, 2, 3, 4, 5}

Final result: [1, 2, 3, 4, 5]

Handling Edge Cases Intuitively

Case 1: One array is empty

arr1 = []
arr2 = [7, 8]

The result is just the unique values of the second array: [7, 8]

Case 2: Both arrays are empty

arr1 = []
arr2 = []

The result is an empty array: []

Case 3: Arrays contain only repeated values

arr1 = [1, 1, 1]
arr2 = [1, 1]

Set will store only one 1, so the result is: [1]

Case 4: Arrays with completely distinct values

arr1 = [10, 20]
arr2 = [30, 40]

No overlap — the result is just a merge of all elements: [10, 20, 30, 40]

Why is This Method Efficient?

Using a set allows for average O(1) time for insertions. So processing both arrays of lengths n and m takes O(n + m) time.

This method is fast, intuitive, and works well even with large arrays.

Algorithm Steps

  1. Given two arrays arr1 and arr2.
  2. Create a set to store unique elements.
  3. Insert all elements of arr1 into the set.
  4. Insert all elements of arr2 into the set.
  5. The set now contains the union of both arrays with no duplicates.
  6. Convert the set to a list (or array) if needed and return it.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool exists(int arr[], int size, int val) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == val) return true;
    }
    return false;
}

void unionOfArrays(int arr1[], int n1, int arr2[], int n2) {
    int result[1000], k = 0;
    for (int i = 0; i < n1; i++) result[k++] = arr1[i];
    for (int i = 0; i < n2; i++) {
        if (!exists(arr1, n1, arr2[i])) result[k++] = arr2[i];
    }
    printf("Union: ");
    for (int i = 0; i < k; i++) printf("%d ", result[i]);
}

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

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n + m)Each element from both arrays is inserted into a set, which takes constant time per insertion on average. Best and worst case remain the same as all elements need to be processed.
Average CaseO(n + m)On average, inserting n elements from the first array and m elements from the second into a set results in linear time complexity.
Worst CaseO(n + m)Even in the worst case (e.g., hash collisions), we must iterate through all elements of both arrays once, so the time remains linear.

Space Complexity

O(n + m)

Explanation: A set is used to store up to all unique elements from both arrays. In the worst case, none of the elements are duplicates, resulting in a total of n + m unique entries.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...