.png)
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
- Brute Force (Nested Loop)
- Using Hashing (Most Efficient)
- Using Sorting + Two Pointers (For Sorted Arrays)
Approach 1: Brute Force Method
Idea
- Add all elements of the first array to a result array
- For each element of the second array:
- Check if it already exists in the result
- Add only if not present
Algorithm
- Create an empty result array
- Insert all elements of arr1
- For each element in arr2, check existence in result
- Add element if not found
Time and Space Complexity
- Time Complexity: O(n * m)
- Space Complexity: O(n + m)
C Implementation
#include<stdio.h>
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
- Create a hash set
- Insert all elements of arr1
- Insert all elements of arr2
- Print all elements from the set
Time and Space Complexity
- Time Complexity: O(n + m)
- Space Complexity: O(n + m)
C++ Implementation
#include<iostream>
#include<unordered_set>
using namespace std;
int main() {
int arr1[] = {1, 2, 3, 4};
int arr2[] = {3, 4, 5, 6};
unordered_set<int> 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
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
