Advertisement
Home Data Structure Arrays Find Union of Two Arrays

Find Union of Two Arrays

1
Advertisement

Title: Find Union of Two Arrays

In this guide, you’ll learn how to find the union of two arrays in Java. The union of two arrays is a new collection that contains every distinct element present in either array, with no duplicates.

This is a popular interview question because it tests whether you know how to remove duplicates efficiently using a Set instead of writing nested loops. By the end of this article you’ll have a complete, working Java program along with a trace of the algorithm, common mistakes to avoid, and a list of edge cases worth testing.

Understanding the Problem

Given two integer arrays, arr1 and arr2, the union is the set of all values that appear in at least one of the arrays. If a value appears in both arrays, or more than once within the same array, it should appear only once in the result.

The order of elements in the union is not strictly defined by the problem, but most implementations either preserve the order elements were first seen or return the result sorted. This article preserves the order of first appearance using a LinkedHashSet.

Approach to Find the Union

Here is the step-by-step approach used to compute the union with a Set:

  1. Create an empty Set<Integer>, specifically a LinkedHashSet, called unionSet to automatically eliminate duplicates while keeping insertion order.
  2. Iterate over every element of arr1 and call unionSet.add(num) for each one.
  3. Iterate over every element of arr2 and add each one to the same unionSet.
  4. Because a Set silently ignores an add call for a value it already contains, duplicates across and within the two arrays are removed automatically.
  5. Allocate an int[] array sized to unionSet.size().
  6. Copy every element out of unionSet into the result array, in iteration order.
  7. Return the result array to the caller.

Java Program

Java
import java.util.LinkedHashSet;
import java.util.Set;

public class UnionOfArrays {

    public static int[] findUnion(int[] arr1, int[] arr2) {
        Set<Integer> unionSet = new LinkedHashSet<>();

        for (int num : arr1) {
            unionSet.add(num);
        }

        for (int num : arr2) {
            unionSet.add(num);
        }

        int[] result = new int[unionSet.size()];
        int index = 0;
        for (int num : unionSet) {
            result[index] = num;
            index++;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {3, 4, 5, 6, 7};

        int[] union = findUnion(arr1, arr2);

        System.out.print("Union of the two arrays: ");
        for (int num : union) {
            System.out.print(num + " ");
        }
    }
}

Explanation of the Program

Let’s walk through what each part of the findUnion method does:

  • unionSet is declared as a LinkedHashSet<Integer> so that duplicate values are rejected automatically and the order elements were first added is preserved.
  • The first for loop iterates over arr1 and calls unionSet.add(num) for every element. Any value already in the set is silently ignored.
  • The second for loop does the same for arr2, adding into the same unionSet so values from both arrays end up in one combined collection.
  • Once both arrays have been processed, unionSet.size() tells us exactly how many distinct values exist, so the result array result can be allocated with the correct length.
  • The final loop copies each value out of unionSet into result in iteration order, and main prints the resulting union.

Step-by-Step Trace

Consider arr1 = {5, 10, 15} and arr2 = {10, 20, 15}. The expected union is {5, 10, 15, 20}. The table below traces every call to unionSet.add(num) in the order it happens:

StepElementAlready in unionSet?unionSet After
15 (from arr1)No{5}
210 (from arr1)No{5, 10}
315 (from arr1)No{5, 10, 15}
410 (from arr2)Yes{5, 10, 15}
520 (from arr2)No{5, 10, 15, 20}
615 (from arr2)Yes{5, 10, 15, 20}

At the end of every step, unionSet holds exactly one copy of every distinct value encountered so far, which is why the duplicate adds at steps 4 and 6 leave the set unchanged.

Examples

Example 1: Arrays With No Common Elements

When the two arrays share nothing in common, the union is simply every element from both arrays combined.

Java
int[] arr1 = {1, 2, 3};
int[] arr2 = {4, 5, 6};

int[] union = findUnion(arr1, arr2);
// union -> [1, 2, 3, 4, 5, 6]

Example 2: Arrays With Overlapping Elements

When values repeat across the two arrays, the shared values appear only once in the union.

Java
int[] arr1 = {1, 2, 3, 4};
int[] arr2 = {3, 4, 5, 6};

int[] union = findUnion(arr1, arr2);
// union -> [1, 2, 3, 4, 5, 6]

Example 3: Arrays of Different Lengths

The two input arrays don’t need to be the same length. The algorithm still produces one combined, duplicate-free result.

Java
int[] arr1 = {7, 8};
int[] arr2 = {7, 8, 9, 10, 11};

int[] union = findUnion(arr1, arr2);
// union -> [7, 8, 9, 10, 11]

Common Mistakes to Avoid

These are the mistakes candidates most often make when solving this exact problem:

  • Checking for duplicates with nested loops – comparing every element of arr1 against every element of arr2 manually works but runs in O(n*m) time. Use a Set so each lookup and insert is O(1) on average.
  • Using a plain HashSet when order matters – a HashSet does not guarantee the union prints in the order elements were first seen. Use LinkedHashSet if insertion order should be preserved.
  • Adding only arr1 into the set – forgetting the second loop over arr2 silently drops every value that only appears in the second array.
  • Calling toArray() and expecting an int[] – Set<Integer>.toArray() returns an Object[] or Integer[], not a primitive int[]. Unbox each element manually or use IntStream to convert.
  • Not checking for a null array reference – passing null for arr1 or arr2 throws a NullPointerException inside the for-each loop. Validate the input before iterating if null is a possibility.

Edge Cases to Test

Walk through these input shapes before you consider the solution complete:

  • Empty arr1
  • Empty arr2
  • Both arrays empty
  • Arrays containing duplicates within themselves
  • Two completely identical arrays
  • Single-element arrays
  • Null array reference
  • Arrays containing Integer.MIN_VALUE or Integer.MAX_VALUE

Additional Considerations

The Set-based approach runs in O(n + m) time, where n and m are the lengths of arr1 and arr2, since every element is inserted into the set exactly once and each insert is O(1) on average.

Space complexity is also O(n + m) in the worst case, when every element across both arrays is distinct. If the input arrays are already sorted, a two-pointer merge that skips duplicates can compute the same union in O(n + m) time without the overhead of hashing, though it requires the inputs to be sorted first.

Interview Follow-up Questions

Once you’ve solved the base problem, expect an interviewer to push further with questions like these:

  • What if the arrays are already sorted? – use a two-pointer merge that advances past equal values, which avoids the overhead of a Set entirely.
  • What if the union must be returned sorted? – insert into a TreeSet<Integer> instead of a LinkedHashSet so the elements come out in ascending order automatically.
  • What if the arrays are too large to fit in memory? – sort each array externally, then merge them in a streaming fashion, writing deduplicated runs to disk instead of holding everything in a single in-memory set.
  • What if you need the union across more than two arrays? – generalize the same accumulation pattern by looping over a list of arrays and adding every element into one shared Set, rather than hardcoding exactly two parameters.

Conclusion

Finding the union of two arrays comes down to one idea: let a Set handle duplicate elimination so you don’t have to write it yourself. The LinkedHashSet-based solution shown here is short, runs in linear time, and is easy to adapt, whether you need a sorted result, a union across more arrays, or a version that handles sorted inputs without hashing.

You can learn more about Array problems: https://dailyjavaconcept.com/category/arrays/