easyArray ProblemsJava

Find the Union of Two Arrays

Return the sorted set of distinct values appearing in either of two arrays.

Quick Answer

Add every element of both arrays to a Set, which discards duplicates automatically. The set then holds each distinct value exactly once; using a TreeSet also returns them in sorted order. This runs in O((m + n) log(m + n)) with a TreeSet, or O(m + n) average with a HashSet.

Problem Statement

Given two integer arrays, return their union: every value that appears in at least one of the arrays, with no duplicates. A value that occurs in both arrays, or multiple times, still appears only once in the union.

For example, the union of [1, 2, 3, 4] and [3, 4, 5, 6] is [1, 2, 3, 4, 5, 6].

Input: Two integer arrays a (length m) and b (length n).

Output: A sorted array of the distinct values found in either input.

Examples

Example 1
Input:  a = [1, 2, 3, 4], b = [3, 4, 5, 6]
Output: [1, 2, 3, 4, 5, 6]

3 and 4 are shared but counted once; 5 and 6 are added from b.

Example 2
Input:  a = [1, 1, 2], b = [2, 3]
Output: [1, 2, 3]

The repeated 1 collapses to one entry; 2 is shared; 3 comes from b.

Constraints

  • 0 <= m, n <= 10^6
  • Values fit in a 32-bit int

Think Before You Code

Reveal the questions to ask yourself first
  • Which data structure removes duplicates for you as you insert?
  • Do you need the output sorted, and if so which set implementation gives that for free?
  • Does inserting the same value twice cause a problem, or is it silently ignored?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
A Set stores each value at most once, so inserting duplicates is harmless.
Hint 2
Add all of array `a`, then all of array `b`, into the same set.
Hint 3
A `TreeSet` keeps its elements sorted, so iterating it yields the union in ascending order.

Approach

Reveal the step-by-step approach

Let a set do the de-duplication.

  1. Create a TreeSet<Integer> (sorted, no duplicates).
  2. Add every element of a to the set.
  3. Add every element of b to the set.
  4. Copy the set into an array; because it is a TreeSet, the result is sorted and duplicate-free.

Each insertion is O(log s) for a TreeSet of size s, so the whole build is O((m + n) log(m + n)); a HashSet would be O(m + n) average but unsorted.

Dry Run

Walk through the example step by step

Union of a = [1, 2, 3, 4], b = [3, 4, 5, 6]:

step         | value | set (sorted)
-------------+-------+-------------------
add a[0]     | 1     | {1}
add a[1]     | 2     | {1,2}
add a[2]     | 3     | {1,2,3}
add a[3]     | 4     | {1,2,3,4}
add b[0]     | 3     | {1,2,3,4}  (already present)
add b[1]     | 4     | {1,2,3,4}  (already present)
add b[2]     | 5     | {1,2,3,4,5}
add b[3]     | 6     | {1,2,3,4,5,6}

Solution

Reveal the full Java solution
import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

public class UnionOfArrays {
    public static int[] union(int[] a, int[] b) {
        Set<Integer> set = new TreeSet<>();
        for (int v : a) {
            set.add(v);
        }
        for (int v : b) {
            set.add(v);
        }
        int[] result = new int[set.size()];
        int k = 0;
        for (int v : set) {
            result[k++] = v;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(
            union(new int[]{1, 2, 3, 4}, new int[]{3, 4, 5, 6}))); // [1, 2, 3, 4, 5, 6]
        System.out.println(Arrays.toString(
            union(new int[]{1, 1, 2}, new int[]{2, 3}))); // [1, 2, 3]
    }
}

A Set enforces uniqueness on insertion, so we never have to check for duplicates by hand — a repeated value is simply ignored. Choosing TreeSet also keeps the elements in sorted order, letting us emit the union directly without a separate sort step. Iterating the set to fill the array is linear in the number of distinct values.

Time: O((m + n) log(m + n)) with TreeSetSpace: O(m + n) for the set and result

Common Mistakes

  • Using nested loops to check membership, which is O(m*n) and needlessly slow.
  • Expecting a HashSet to give sorted output; only a TreeSet or an explicit sort does.

Edge Cases to Test

  • Both arrays empty should return an empty array.
  • Identical arrays should return their distinct elements once.
  • Arrays with internal duplicates must still collapse to single entries.

Interview Follow-Ups

  • How would you compute the union while preserving first-seen insertion order?
  • How would you find the intersection of the two arrays instead?
  • How would the approach change if the inputs were already sorted?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us