Problem Statement
Given two integer arrays, return their union, including duplicate elements. The result should preserve the order of elements as they appear in the input arrays.
Example 1:
Input: arr1 = [1, 2, 3, 4], arr2 = [3, 4, 5, 6]
Output: [1, 2, 3, 4, 3, 4, 5, 6]
Example 2:
Input: arr1 = [7, 8, 9], arr2 = [10, 11]
Output: [7, 8, 9, 10, 11]
Approach 1: Using List and AddAll (Preserve Duplicates)
Step 1: Create a List<Integer> to store the union.
Step 2: Add all elements from arr1 to the list.
Step 3: Add all elements from arr2 to the list.
Step 4: Convert the list back to an array if required.
Implementation:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class UnionWithDuplicates {
public static List<Integer> unionWithDuplicates(int[] arr1, int[] arr2) {
List<Integer> result = new ArrayList<>();
for (int num : arr1) {
result.add(num);
}
for (int num : arr2) {
result.add(num);
}
return result;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 4};
int[] arr2 = {3, 4, 5, 6};
List<Integer> union = unionWithDuplicates(arr1, arr2);
System.out.println(union); // Output: [1, 2, 3, 4, 3, 4, 5, 6]
}
}
Time Complexity:
O(N + M) where N is the size of arr1 and M is the size of arr2.
Space Complexity:
O(N + M) for storing the result list.
Approach 2: Using Array Concatenation
If you only need an array and do not require a list, you can concatenate both arrays.
import java.util.Arrays;
public class UnionWithDuplicates {
public static int[] unionWithDuplicates(int[] arr1, int[] arr2) {
int[] result = new int[arr1.length + arr2.length];
System.arraycopy(arr1, 0, result, 0, arr1.length);
System.arraycopy(arr2, 0, result, arr1.length, arr2.length);
return result;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 4};
int[] arr2 = {3, 4, 5, 6};
int[] union = unionWithDuplicates(arr1, arr2);
System.out.println(Arrays.toString(union)); // Output: [1, 2, 3, 4, 3, 4, 5, 6]
}
}
Time Complexity:
O(N + M) (Copying elements using System.arraycopy is efficient).
Space Complexity:
O(N + M) (New array is created).
