1. Overview
In this tutorial, we’ll explore various methods of merging the contents of two arrays and subsequently eliminating the duplicates. It is similar to a union operation:
For this, we’ll consider two arrays of integers. Basically, if the following are the two arrays:
- arr1 = { 3, 2, 1, 4, 5, 6, 8, 7, 6, 9 }
- arr2 = { 8, 9, 10, 11, 12, 13, 15, 14, 15, 14, 16, 17 }
Then the result should be:
- mergedArray = { 3, 2, 1, 4, 5, 6, 8, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17 }
2. Approach with Basic Array Operations
Normally, this requirement can be implemented by using Set or Stream API, explained in the later sections. But those libraries are resource-intensive. Hence, we’ll focus more on a traditional approach by using basic array operations while iterating through it.
2.1. Approach for Unsorted Arrays
First, let’s define a function that would merge the arrays. Then, we’ll create a method to remove the duplicates from it. Alternatively, we can remove the duplicates from the arrays and then merge them. But this won’t make much of a difference with respect to performance.
Hence, let’s begin with the method that merges two arrays:
static int[] mergeArrays(int[] arr1, int[] arr2) {
int[] mergedArrays = new int[arr1.length + arr2.length];
System.arraycopy(arr1, 0, mergedArrays, 0, arr1.length);
System.arraycopy(arr2, 0, mergedArrays, arr1.length, arr2.length);
return mergedArrays;
}
Going forward, we’re going to use the above method for merging the arrays in all the sections.
Now, let’s implement the method to remove the duplicates from the merged arrays:
static int[] removeDuplicate(int[] arr) {
int[] withoutDuplicates = new int[arr.length];
int i = 0;
for (int element : arr) {
if (!isElementPresent(withoutDuplicates, element)) {
withoutDuplicates[i] = element;
i++;
}
}
int[] truncatedArray = new int[i];
System.arraycopy(withoutDuplicates, 0, truncatedArray, 0, i);
return truncatedArray;
}
static boolean isElementPresent(int[] arr, int element) {
for (int el : arr) {
if (el == element) {
return true;
}
}
return false;
}
In the above method, removeDuplicate(), the withoutDuplicates array is populated with the elements of the merged array only if the element is not pre-existing in it.
By using the above methods, let’s define mergeAndRemoveDuplicates():
public static int[] mergeAndRemoveDuplicates(int[] arr1, int[] arr2) {
return removeDuplicate(mergeArrays(arr1, arr2));
}
Let’s see how that works:
@Test
public void givenNoLibraryAndUnSortedArrays_whenArr1andArr2_thenMergeAndRemoveDuplicates() {
int[] arr1 = {3, 2, 1, 4, 5, 6, 8, 7, 9};
int[] arr2 = {8, 9, 10, 11, 12, 13, 15, 14, 15, 14, 16, 17};
int[] expectedArr = {3, 2, 1, 4, 5, 6, 8, 7, 9, 10, 11, 12, 13, 15, 14, 16, 17};
int[] mergedArr = MergeArraysAndRemoveDuplicate.mergeAndRemoveDuplicates(arr1, arr2);
assertArrayEquals(expectedArr, mergedArr);
}
It proves we achieved the expected result. Interestingly, this approach preserves the order of the array elements as well.
Since removing duplicates involves comparing each element in the merged array with all other elements, the time complexity of this approach is close to O(n x n).
2.2. Approach for Sorted Arrays
Let’s consider a scenario where the elements are already sorted in the array. Also, in the second array, the first element is equal to or greater than the last element of the first array.
In such a case, we can use the following method to get rid of duplicate elements:
public static int[] removeDuplicateOnSortedArray(int[] arr) {
int[] uniqueArray = new int[arr.length];
uniqueArray[0] = arr[0];
int uniqueCount = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] != arr[i - 1]) {
uniqueArray[uniqueCount] = arr[i];
uniqueCount++;
}
}
int[] truncatedArray = new int[uniqueCount];
System.arraycopy(uniqueArray, 0, truncatedArray, 0, uniqueCount);
return truncatedArray;
}
This approach is more efficient because it only compares adjacent elements. If they are not equal, they are added to the uniqueArray array. In contrast, earlier, the isElementPresent() method compared the array element with all the other elements in the array.
Let’s see removeDuplicateOnSortedArray() in action:
@Test
public void givenNoLibraryAndSortedArrays_whenArr1andArr2_thenMergeAndRemoveDuplicates() {
int[] arr1 = {1, 2, 3, 4, 5, 5, 6, 7, 7, 8};
int[] arr2 = {8, 9, 10, 11, 12, 13, 14, 15, 15, 16, 17};
int[] expectedArr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
int[] mergedArr = MergeArraysAndRemoveDuplicate.mergeAndRemoveDuplicatesOnSortedArray(arr1, arr2);
assertArrayEquals(expectedArr, mergedArr);
}
In a worst-case scenario, the time complexity of this approach is O(n).
3. Merge Arrays Using Set
The Set doesn’t allow duplicate elements. Hence, this feature helps remove duplicates.
Let’s have a look at the method mergeAndRemoveDuplicatesUsingSet():
public static int[] mergeAndRemoveDuplicatesUsingSet(int[] arr1, int[] arr2) {
int[] mergedArr = mergeArrays(arr1, arr2);
Set<Integer> uniqueInts = new HashSet<>();
for (int el : mergedArr) {
uniqueInts.add(el);
}
return getArrayFromSet(uniqueInts);
}
While adding the array elements into the Set uniqueInts, the elements are ignored if they are already present init. At the end, getArrayFromSet() converts the Set into an array.
Let’s see how the above method behaves:
@Test
public void givenSet_whenArr1andArr2_thenMergeAndRemoveDuplicates() {
int[] arr1 = {3, 2, 1, 4, 5, 6, 8, 7, 9};
int[] arr2 = {8, 9, 10, 11, 12, 13, 15, 14, 15, 14, 16, 17};
int[] expectedArr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
int[] mergedArr = MergeArraysAndRemoveDuplicate.mergeAndRemoveDuplicatesUsingSet(arr1, arr2);
assertArrayEquals(expectedArr, mergedArr);
}
It’s evident. that the arrays no longer preserve the order of the elements.
The execution time with this approach is dependent on the number of array elements. Hence, its time complexity is O(n).
4. Merge Arrays Using Stream
The powerful Stream API provides a very concise and declarative way of merging and removing duplicates from the arrays. For further details, let’s check out the method mergeAndRemoveDuplicatesUsingStream():
public static int[] mergeAndRemoveDuplicatesUsingStream(int[] arr1, int[] arr2) {
Stream<Integer> s1 = Arrays.stream(arr1).boxed();
Stream<Integer> s2 = Arrays.stream(arr2).boxed();
return Stream.concat(s1, s2)
.distinct()
.mapToInt(Integer::intValue)
.toArray();
}
Firstly, the arrays are converted individually into Stream. Then, the boxed method wraps the int elements in the arrays as Integer. Further, the Stream pipeline merges the arrays and then eliminates the duplicates from them.
Let’s see how it works:
@Test
public void givenStream_whenArr1andArr2_thenMergeAndRemoveDuplicates() {
int[] arr1 = {3, 2, 1, 4, 5, 6, 8, 7, 9};
int[] arr2 = {8, 9, 10, 11, 12, 13, 15, 14, 15, 14, 16, 17};
int[] expectedArr = {3, 2, 1, 4, 5, 6, 8, 7, 9, 10, 11, 12, 13, 15, 14, 16, 17};
int[] mergedArr = MergeArraysAndRemoveDuplicate.mergeAndRemoveDuplicatesUsingStream(arr1, arr2);
assertArrayEquals(expectedArr, mergedArr);
}
It’s evident that the Stream approach preserves the order of the elements in the array.
The dominant factor in deciding the time complexity is the distinct()Â method in the stream, which is O(n). Overall, we can say that the time complexity of this approach is O(n).
5. Conclusion
In this tutorial, we examined various ways to merge two arrays and then remove the duplicates from them. The most concise approach uses Stream API. The set doesn’t preserve the order of the elements inserted in them. However, Set is extremely effective in removing duplicates. The other two approaches preserve the order of the elements in the array.
It is worth noting that Stream and Set are quite resource-intensive, and hence, it is advisable to avoid them wherever possible.
As usual, the code examples are available over on GitHub.
