Data Structures and Algorithms (DSA)  

🔗 Finding the Union of Two Arrays in DSA

📝 Introduction

In DSA, array operations are fundamental. One frequently asked question in coding interviews is finding the union of two arrays. The union of two arrays includes all distinct elements from both arrays.

For example

Array1: [1, 2, 3, 4]  
Array2: [3, 4, 5, 6]  
Union: [1, 2, 3, 4, 5, 6]

⚡ Methods to Find the Union

1️⃣ Using a Hash Set (Efficient Approach)

A HashSet automatically stores unique elements. This approach works well in most programming languages like C++, Java, and Python.

Steps

  1. Create an empty hash set.

  2. Add all elements of the first array to the set.

  3. Add all elements of the second array to the set.

  4. The set now contains all unique elements (union).

Example in Python

def union_arrays(arr1, arr2):
    union_set = set(arr1) | set(arr2)  # Using set union operator
    return list(union_set)

arr1 = [1, 2, 3, 4]
arr2 = [3, 4, 5, 6]
print(union_arrays(arr1, arr2))  # Output: [1, 2, 3, 4, 5, 6]

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

2️⃣ Using Sorting & Two Pointers

If you cannot use extra space, you can sort both arrays and use two pointers to find the union.

Steps

  1. Sort both arrays.

  2. Use two pointers to traverse the arrays.

  3. Compare elements and add the smaller one to the union array.

  4. If elements are equal, add one element and move both pointers.

Example in Python

def union_sorted(arr1, arr2):
    arr1.sort()
    arr2.sort()
    i = j = 0
    union_arr = []

    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            union_arr.append(arr1[i])
            i += 1
        elif arr1[i] > arr2[j]:
            union_arr.append(arr2[j])
            j += 1
        else:
            union_arr.append(arr1[i])
            i += 1
            j += 1

    while i < len(arr1):
        union_arr.append(arr1[i])
        i += 1
    while j < len(arr2):
        union_arr.append(arr2[j])
        j += 1

    return union_arr

arr1 = [1, 2, 3, 4]
arr2 = [3, 4, 5, 6]
print(union_sorted(arr1, arr2))  # Output: [1, 2, 3, 4, 5, 6]

Time Complexity: O(n log n + m log m) (for sorting)
Space Complexity: O(n + m)

3️⃣ Using Brute Force (Not Recommended)

In brute force, you can combine both arrays and then remove duplicates. This is less efficient but easy to implement.

✅ Applications of the Union of Arrays

  • Set operations in programming (union, intersection, difference).

  • Database queries (merging two datasets without duplicates).

  • Coding interviews — common array problem to test logic and efficiency.

💡 Tips & Tricks

  • Use a hash set when time efficiency matters.

  • Use sorting + two pointers when memory usage is critical.

  • Always clarify with the interviewer whether duplicate elements are allowed.

🎯 Conclusion

Finding the union of two arrays is a foundational DSA problem. Using hash sets provides a fast and simple solution, while sorting with two pointers offers a space-efficient alternative. Mastering this problem helps in solving many array-based problems in interviews and real-world applications.

Membership not found