701730. Union of Arrays with Duplicates
Union of Arrays with Duplicates
Slug: union-of-two-arrays3538 Difficulty: Easy Id: 701730 Topic Tags: Hash, Data Structures, Algorithms, Arrays Company Tags: Zoho, Rockstand
Summary
The problem is about finding the union of two arrays with duplicates. The goal is to combine both arrays and remove any duplicate elements. This problem involves basic array manipulation and hash table concepts.
Detailed Explanation
To solve this problem, we can use a simple approach by iterating through both arrays and adding unique elements from each array into a new set (or array). We can use a hash table (like HashMap in Java or dictionary in Python) to keep track of the unique elements.
Here's the step-by-step breakdown:
- Create an empty hash table (HashMap or dictionary).
- Iterate through the first array and add each element to the hash table if it doesn't already exist.
- Repeat step 2 for the second array.
- Return the keys of the hash table as the union of both arrays.
Here's a diagram illustrating this process:
Array 1: [a, b, c]
Array 2: [c, d, e]
Union:
Hash Table (keys): [a, b, c, d, e]
The time complexity for this solution is O(n), where n is the total number of elements in both arrays. The space complexity is also O(n) because we're storing all unique elements in the hash table.
Optimized Solutions
Java
import java.util.HashMap;
import java.util.Map;
public class UnionOfArrays {
public static int[] union(int[] arr1, int[] arr2) {
Map<Integer, Boolean> map = new HashMap<>();
for (int i : arr1) {
map.put(i, true);
}
for (int j : arr2) {
if (!map.containsKey(j)) {
map.put(j, true);
}
}
int[] result = new int[map.size()];
int i = 0;
for (Map.Entry<Integer, Boolean> entry : map.entrySet()) {
result[i] = entry.getKey();
i++;
}
return result;
}
}