Java - Union of Arrays with Duplicates

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).