Union of Two Arrays using Set - Optimal Approach

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace

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

Visualization Player

Solution❯

To find the union of two arrays means to combine all values that are present in either of the arrays, but without repeating any value. This is especially important when the arrays have duplicate values — we want each element to appear only once in the result.

The most efficient way to do this is by using a Set data structure. Sets automatically discard duplicate values, so you can insert all elements from both arrays into the set, and it will ensure that only unique values are kept.

What if both arrays are normal (non-empty)?

If both arr1 and arr2 contain values — whether overlapping or not — adding all elements to a set will result in a list of all distinct elements. For example, if arr1 = [1, 2, 3] and arr2 = [3, 4, 5], the union will be [1, 2, 3, 4, 5]. The duplicate 3 is included only once.

What if one array is empty?

If either arr1 or arr2 is empty, then the union is simply the unique values from the non-empty array. For example, if arr1 = [] and arr2 = [7, 8], the union will be [7, 8].

What if both arrays are empty?

If both arrays are empty, then there are no values to include in the union. So the result will also be an empty array: [].

What if arrays have only repeated values?

If both arrays contain only repeated values — even if they are the same — the union result will include just that one value. For instance, arr1 = [1, 1, 1] and arr2 = [1, 1] → union is [1].

Why is this method optimal?

Using a Set helps us achieve optimal performance because inserting into a set has an average time complexity of O(1) per element. So the overall time complexity becomes O(n + m), where n and m are the lengths of the two arrays.

This makes the solution both simple to implement and highly efficient, even for large input sizes.

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

Python
JavaScript
Java
C++
C
def union_of_arrays(arr1, arr2):
    result = set()
    for num in arr1:
        result.add(num)
    for num in arr2:
        result.add(num)
    return list(result)

# Sample Input
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
print("Union:", union_of_arrays(arr1, arr2))

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.