Backend interview prep

Start Learning

Union of Two Arrays

Java coding interview problem for Array Coding: Union of Two Arrays.

Finding the union of two arrays is one of the most common array interview questions.

This problem helps you understand:

  • Set Operations
  • Hashing
  • Duplicate Handling
  • Sorting
  • Two Pointer Technique
  • Java Collections
  • Time Complexity Optimization

Union operations are heavily used in:

  • Database systems
  • Data analytics
  • Search engines
  • Recommendation systems
  • Distributed systems

What is Union of Two Arrays?

The union of two arrays means combining all unique elements from both arrays.

In simple words:

Union contains every element that appears in either array, without duplicates.

Example

Array 1:

[1,2,3,4]

Array 2:

[3,4,5,6]

Union:

[1,2,3,4,5,6]

Explanation:

Common elements:

3,4

are included only once.

Mathematical Representation

Union is represented as:

A ∪ B

Meaning:

All elements present in:

A

OR

B

Example:

A = {1,2,3}

B = {3,4,5}

Union:

A ∪ B = {1,2,3,4,5}

Union vs Intersection

A common interview confusion is the difference between union and intersection.

Union

Contains all unique elements.

Example:

A:

[1,2,3]


B:

[3,4,5]

Result:

[1,2,3,4,5]

Intersection

Contains only common elements.

Example:

A:

[1,2,3]


B:

[3,4,5]

Result:

[3]

Types of Array Union

There are two common interpretations.

1. Unique Union

Duplicates are removed.

Example:

Array 1:

[1,2,2,3]

Array 2:

[2,3,4]

Output:

[1,2,3,4]

2. Union With Duplicates

Duplicate occurrences are preserved.

Example:

Array 1:

[1,2,2,3]

Array 2:

[2,3,4]

Output:

[1,2,2,2,3,3,4]

Most interview questions expect:

Unique Union

Always clarify with the interviewer.

Why is This Question Asked in Interviews?

Interviewers ask union problems because they test:

  • Java Collections knowledge
  • HashSet understanding
  • Duplicate removal
  • Sorting algorithms
  • Optimization skills

It is a foundation for:

  • Merge operations
  • Database UNION queries
  • Data synchronization
  • Comparing datasets

Real-World Applications

Database UNION Operation

Combining records from multiple tables.

Example:

Customers from System A:

[101,102,103]

Customers from System B:

[103,104,105]

Combined customers:

[101,102,103,104,105]

Social Media

Combining followers from different platforms.

Instagram followers:

[John,Mike,Alex]

Twitter followers:

[Alex,David,Sam]

Union:

[John,Mike,Alex,David,Sam]

Search Systems

Combining search results from multiple sources.

Source 1:

Java Tutorial

Spring Boot Guide

Source 2:

Java Tutorial

AWS Guide

Union:

Java Tutorial

Spring Boot Guide

AWS Guide

Data Migration

Combining records from multiple systems while removing duplicates.

Problem Statement

Given two integer arrays,

find their union.

Return all unique elements present in both arrays.

Example 1

Input:

Array 1:

[1,2,3]


Array 2:

[3,4,5]

Output:

[1,2,3,4,5]

Example 2

Input:

Array 1:

[10,20,20]


Array 2:

[20,30,40]

Output:

[10,20,30,40]

Example 3

Input:

Array 1:

[]


Array 2:

[1,2,3]

Output:

[1,2,3]

Understanding Union

Consider:

Array A:

[10,20,30,40]

Array B:

[30,40,50,60]

Start:

Result = []

Add Array A elements:

[10,20,30,40]

Add Array B elements:

30 → Already exists

40 → Already exists

50 → Add

60 → Add

Final:

[10,20,30,40,50,60]

Array Visualization

Input:

Array A

[1,2,3,4]


Array B

[3,4,5,6]

Union:

1 2 3 4

+

      5 6

Result:

[1,2,3,4,5,6]

Dry Run

Input:

A = [5,10,15]

B = [10,20,25]

Create result:

[]

Process A:

Element Result Action
5 [5] Add
10 [5,10] Add
15 [5,10,15] Add

Process B:

Element Result Action
10 [5,10,15] Duplicate
20 [5,10,15,20] Add
25 [5,10,15,20,25] Add

Final:

[5,10,15,20,25]

Approach 1 — Using HashSet (Recommended)

The most common interview solution uses HashSet.

Why?

Because HashSet:

  • Removes duplicates automatically.
  • Provides fast insertion.
  • Provides fast lookup.

Algorithm

  1. Create a HashSet.
  2. Add all elements from first array.
  3. Add all elements from second array.
  4. Convert Set into array.
  5. Return result.

Java Program

import java.util.*;

public class UnionOfArraysHashSet {


    public static int[] union(
            int[] nums1,
            int[] nums2) {


        Set<Integer> result =
                new HashSet<>();


        for (int number : nums1) {

            result.add(number);

        }


        for (int number : nums2) {

            result.add(number);

        }


        return result.stream()
                .mapToInt(Integer::intValue)
                .toArray();

    }


    public static void main(String[] args) {


        int[] nums1 =
                {1,2,3};


        int[] nums2 =
                {3,4,5};


        System.out.println(
                Arrays.toString(
                        union(nums1, nums2)));

    }

}

Output

[1,2,3,4,5]

Step-by-Step Explanation

Create Set:

Set<Integer> result =
        new HashSet<>();

Add first array:

[1,2,3]

Set:

{1,2,3}

Add second array:

[3,4,5]

Processing:

3 → Already exists

4 → Add

5 → Add

Final:

{1,2,3,4,5}

Advantages

  • Simplest solution.
  • Removes duplicates automatically.
  • Works with unsorted arrays.
  • Average O(1) insertion.

Drawbacks

  • Does not maintain insertion order.
  • Requires extra memory.
  • Hashing overhead.

Complexity Analysis

Let:

n = size of first array

m = size of second array

Time:

O(n + m)

Why?

Each element is inserted once.

Space:

O(n + m)

For storing unique values.

Approach 2 — Using LinkedHashSet (Preserve Order)

LinkedHashSet works like HashSet but maintains insertion order.

Example:

Input:

A:

[5,2,3]


B:

[3,7,1]

HashSet:

[1,2,3,5,7]

Order is not guaranteed.

LinkedHashSet:

[5,2,3,7,1]

Original insertion order is maintained.

Java Program

import java.util.*;

public class UnionOfArraysLinkedHashSet {


    public static Integer[] union(
            Integer[] nums1,
            Integer[] nums2) {


        Set<Integer> result =
                new LinkedHashSet<>();


        for (int number : nums1) {

            result.add(number);

        }


        for (int number : nums2) {

            result.add(number);

        }


        return result.toArray(
                new Integer[0]);

    }


    public static void main(String[] args) {


        Integer[] nums1 =
                {5,2,3};


        Integer[] nums2 =
                {3,7,1};


        System.out.println(
                Arrays.toString(
                        union(nums1, nums2)));

    }

}

Output

[5,2,3,7,1]

Advantages

  • Removes duplicates.
  • Maintains order.
  • Better for user-facing output.

Drawbacks

  • Uses more memory than HashSet.
  • Slightly slower.

HashSet vs LinkedHashSet

Feature HashSet LinkedHashSet
Duplicate Removal Yes Yes
Order Maintained No Yes
Performance Faster Slightly slower
Memory Less More

Approach 3 — Using Two Pointer Approach (Optimal for Sorted Arrays)

The Two Pointer technique is an efficient approach to find the union of two arrays when both arrays are sorted.

Instead of using extra memory like HashSet,

we compare both arrays directly.

Requirement

The arrays must be sorted.

Example:

Array 1:

[1,2,3,4,5]

Array 2:

[2,3,4,6,7]

Two Pointer Concept

Maintain two pointers:

i → First array pointer

j → Second array pointer

Compare:

nums1[i]

with

nums2[j]

Case 1

If:

nums1[i] < nums2[j]

Add nums1 element.

Move:

i++

Case 2

If:

nums1[i] > nums2[j]

Add nums2 element.

Move:

j++

Case 3

If:

nums1[i] == nums2[j]

Add element once.

Move both:

i++

j++

Visualization

Input:

nums1:

[1,2,3,4,5]


nums2:

[2,3,4,6,7]

Pointers:

 i

[1,2,3,4,5]


 j

[2,3,4,6,7]

Compare:

1 < 2

Add:

[1]

Move i.

Compare:

2 == 2

Add:

[1,2]

Move both.

Compare:

3 == 3

Add:

[1,2,3]

Continue:

Final:

[1,2,3,4,5,6,7]

Algorithm

  1. Sort both arrays.
  2. Create two pointers.
  3. Compare current values.
  4. Add smaller value.
  5. If equal, add once.
  6. Remove duplicates.
  7. Return union.

Java Program

import java.util.*;

public class UnionOfArraysTwoPointer {


    public static int[] union(
            int[] nums1,
            int[] nums2) {


        Arrays.sort(nums1);

        Arrays.sort(nums2);


        List<Integer> result =
                new ArrayList<>();


        int i = 0;

        int j = 0;


        while (i < nums1.length &&
                j < nums2.length) {


            int value;


            if (nums1[i] < nums2[j]) {

                value = nums1[i++];

            } else if (nums1[i] > nums2[j]) {

                value = nums2[j++];

            } else {

                value = nums1[i];

                i++;

                j++;

            }


            if (result.isEmpty() ||
                    result.get(result.size() - 1)
                            != value) {

                result.add(value);

            }

        }


        while (i < nums1.length) {

            if (result.isEmpty() ||
                    result.get(result.size() - 1)
                            != nums1[i]) {

                result.add(nums1[i]);

            }

            i++;

        }


        while (j < nums2.length) {

            if (result.isEmpty() ||
                    result.get(result.size() - 1)
                            != nums2[j]) {

                result.add(nums2[j]);

            }

            j++;

        }


        return result.stream()
                .mapToInt(Integer::intValue)
                .toArray();

    }


    public static void main(String[] args) {


        int[] nums1 =
                {1,2,3,4};


        int[] nums2 =
                {3,4,5,6};


        System.out.println(
                Arrays.toString(
                        union(nums1, nums2)));

    }

}

Output

[1,2,3,4,5,6]

Step-by-Step Explanation

Input:

nums1:

[1,2,3,4]


nums2:

[3,4,5,6]

Compare:

1 and 3

Add:

1

Compare:

2 and 3

Add:

2

Compare:

3 and 3

Add:

3

Move both.

Compare:

4 and 4

Add:

4

Remaining:

5,6

Add.

Result:

[1,2,3,4,5,6]

Complexity Analysis

Sorting:

O(n log n + m log m)

Traversal:

O(n + m)

Overall:

O(n log n + m log m)

Space:

O(1)

excluding output storage.

Advantages

  • No HashSet required.
  • Memory efficient.
  • Good for sorted arrays.
  • Linear traversal after sorting.

Drawbacks

  • Requires sorting.
  • Sorting changes original arrays.
  • More code than HashSet.

Approach 4 — Using Sorting Approach

Another approach is:

  1. Combine both arrays.
  2. Sort combined array.
  3. Remove duplicates.

Example

Input:

A:

[5,2,1]


B:

[2,4,5]

Combine:

[5,2,1,2,4,5]

Sort:

[1,2,2,4,5,5]

Remove duplicates:

[1,2,4,5]

Java Program

import java.util.*;

public class UnionOfArraysSorting {


    public static int[] union(
            int[] nums1,
            int[] nums2) {


        int[] combined =
                new int[nums1.length +
                        nums2.length];


        int index = 0;


        for (int n : nums1) {

            combined[index++] = n;

        }


        for (int n : nums2) {

            combined[index++] = n;

        }


        Arrays.sort(combined);


        List<Integer> result =
                new ArrayList<>();


        for (int number : combined) {


            if (result.isEmpty() ||
                    result.get(result.size() - 1)
                            != number) {


                result.add(number);

            }

        }


        return result.stream()
                .mapToInt(Integer::intValue)
                .toArray();

    }

}

Complexity Analysis

Combine:

O(n+m)

Sorting:

O((n+m) log(n+m))

Space:

O(n+m)

Advantages

  • Simple logic.
  • Easy to implement.
  • Sorting makes duplicates easy to remove.

Drawbacks

  • Uses extra array.
  • Slower than HashSet.
  • Not memory efficient.

Approach 5 — Using Java Streams

Java Streams provide a concise way to implement union.

The idea:

  1. Combine streams.
  2. Apply distinct().
  3. Convert back to array.

Java Program

import java.util.Arrays;
import java.util.stream.IntStream;

public class UnionOfArraysStreams {


    public static int[] union(
            int[] nums1,
            int[] nums2) {


        return IntStream.concat(
                    Arrays.stream(nums1),
                    Arrays.stream(nums2))
                .distinct()
                .toArray();

    }


    public static void main(String[] args) {


        int[] nums1 =
                {1,2,3};


        int[] nums2 =
                {3,4,5};


        System.out.println(
                Arrays.toString(
                        union(nums1, nums2)));

    }

}

Output

[1,2,3,4,5]

Step-by-Step Explanation

Combine arrays:

[1,2,3,3,4,5]

Apply:

distinct()

Result:

[1,2,3,4,5]

Advantages

  • Very clean syntax.
  • Modern Java approach.
  • Preserves encounter order.

Drawbacks

  • Stream overhead.
  • Uses additional memory internally.
  • Less suitable for algorithm learning.

Internal Working of HashSet

HashSet internally uses:

HashMap

structure.

When adding:

set.add(value);

Java calculates:

hashCode()

and stores the value in a bucket.

Example:

set.add(10);

Internally:

10

↓

hashCode()

↓

Bucket location

Benefits:

  • Fast insertion.
  • Fast search.
  • Duplicate detection.

Average complexity:

O(1)

Handling Duplicate Elements

Interview clarification:

Should union contain duplicates?

Unique Union

Example:

A:

[1,2,2]


B:

[2,3]

Output:

[1,2,3]

Use:

  • HashSet
  • LinkedHashSet
  • Streams distinct()

Union With Duplicates

Example:

A:

[1,2,2]


B:

[2,3]

Output:

[1,2,2,2,3]

Use:

  • Frequency HashMap

Primitive vs Object Arrays

Primitive Array

Example:

int[]

Advantages:

  • Faster.
  • Less memory.
  • No boxing.

Object Array

Example:

Integer[]

Advantages:

  • Works with Collections.
  • Supports generics.

Comparison of All Approaches

Approach Time Complexity Space Order Best Use Case
HashSet O(n+m) O(n+m) No General solution
LinkedHashSet O(n+m) O(n+m) Yes Preserve order
Two Pointer O(n log n + m log m) O(1) Sorted Memory efficient
Sorting O((n+m)log(n+m)) O(n+m) Sorted Simple implementation
Streams O(n+m) O(n+m) Yes Modern Java

Common Interview Mistakes

Mistake 1

Confusing union with intersection.

Union:

All unique elements

Intersection:

Only common elements

Mistake 2

Ignoring duplicates.

Always clarify:

Unique union?

or

Duplicate union?

Mistake 3

Assuming HashSet maintains order.

Use:

LinkedHashSet

for insertion order.

Mistake 4

Using nested loops.

Complexity:

O(n*m)

Avoid unless data is very small.

Mistake 5

Sorting without considering modification.

Arrays.sort(array);

changes input.

Edge Cases

Input Output
[],[] []
[1],[1] [1]
[1,2],[3,4] [1,2,3,4]
Negative numbers Works
Large arrays Choose optimized approach

Interview Follow-up Questions

Q1. Difference between union and intersection?

Q2. Find union without extra space.

Q3. Find union of three arrays.

Q4. Preserve insertion order.

Q5. How does HashSet remove duplicates?

Q6. Implement database UNION operation.

Q7. Find union with duplicate counts.

Q8. Merge multiple sorted arrays.

Related Problems

  • Intersection of Two Arrays
  • Remove Duplicates
  • Merge Sorted Arrays
  • Two Sum
  • Frequency Counting
  • Find Duplicate Elements
  • Common Elements in Multiple Arrays

Key Takeaways

  • Union combines all unique elements from two arrays.
  • HashSet is the most common interview solution.
  • LinkedHashSet preserves insertion order.
  • Two Pointer is best when arrays are already sorted.
  • Sorting helps simplify duplicate removal.
  • Always clarify duplicate requirements.

Frequently Asked Interview Questions

Q1. Which approach is best?

For general unsorted arrays:

HashSet

For sorted arrays:

Two Pointer

Q2. Why use HashSet?

Because duplicate removal and lookup are efficient.

Average:

O(1)

Q3. Why use LinkedHashSet?

When output order matters.

Q4. Can union be solved without extra memory?

Yes.

Use:

Sorted arrays + Two Pointer

Q5. What is production recommendation?

Choose based on requirements:

  • Fast development → HashSet
  • Ordered output → LinkedHashSet
  • Memory optimization → Two Pointer
  • Functional style → Streams

Interview Tip

When asked:

"Find union of two arrays."

Clarify:

  1. Are arrays sorted?
  2. Should duplicates be removed?
  3. Is order important?
  4. Is extra memory allowed?

Then explain:

  1. HashSet solution
  2. LinkedHashSet for ordering
  3. Two Pointer for sorted arrays
  4. Sorting approach
  5. Streams approach

Understanding these trade-offs demonstrates strong knowledge of Java Collections, algorithms, and real-world engineering decisions.