Find Unique Elements in an Array in Java

How to Find Unique Elements in an Array in Java

"Unique" is one of those words in programming that has a more specific meaning than it does in everyday language. Understanding that distinction is important before writing any code. This guide explains what "unique elements" really means in array problems and covers the standard approaches, including a clever XOR trick for a common interview variation.

Problem Statement

Given an array like {4, 2, 4, 7, 2, 4, 8}, the unique elements (elements appearing exactly once) are:

7
8

This is different from the distinct elements, which are:

4
2
7
8

Unique vs Distinct: An Important Distinction

These two terms are often confused, but they mean different things.

Distinct Elements

Distinct elements are every different value that appears in the array, regardless of how many times each value occurs.

Example:

{4, 2, 4, 7}

Distinct elements are:

4, 2, 7

Unique Elements

Unique elements are values that appear exactly once.

Example:

{4, 2, 4, 7}

Unique elements are:

2, 7

Whenever you encounter this problem, clarify whether the requirement is to find unique elements or distinct elements, since the solutions are different.

Method 1: Using HashMap Frequency Count (General Solution)

import java.util.HashMap;
import java.util.Map;

int[] numbers = {4, 2, 4, 7, 2, 4, 8};

Map<Integer, Integer> frequencyMap = new HashMap<>();

for (int num : numbers) {
    frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}

System.out.println("Unique elements:");

for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
    if (entry.getValue() == 1) {
        System.out.println(entry.getKey());
    }
}

This is the standard solution. It first counts the frequency of every element and then prints only those whose frequency is exactly one.

Method 2: Using Java Streams

import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

Map<Integer, Long> frequencyMap = Arrays.stream(numbers)
        .boxed()
        .collect(Collectors.groupingBy(
                n -> n,
                Collectors.counting()
        ));

frequencyMap.entrySet()
        .stream()
        .filter(entry -> entry.getValue() == 1)
        .map(Map.Entry::getKey)
        .forEach(System.out::println);

This solution uses Java Streams to build the frequency map and then filters elements whose count is exactly one.

Method 3: The XOR Trick (Special Case)

This technique works only when every element appears exactly twice except one unique element.

int[] numbers = {4, 2, 7, 2, 4};

int result = 0;

for (int num : numbers) {
    result ^= num;
}

System.out.println("Unique element: " + result);

Output:

Unique element: 7

The XOR operator works because:

• x ^ x = 0
• x ^ 0 = x

Every repeated element cancels itself, leaving only the single unmatched value.

Step-by-Step Explanation

HashMap Solution

A frequency map is created by counting how many times every element appears.

After counting is complete, only elements with a frequency of exactly one are printed.

This approach works regardless of how many times duplicate elements occur.

XOR Solution

The XOR trick is much more specialized.

As every repeated value appears exactly twice, each pair cancels itself during the XOR operation, leaving only the unique element.

This method does not work if:

• More than one element is unique.
• An element appears three or more times.

Internal Working (Memory View)

Consider the array:

{4, 2, 7, 2, 4}

The XOR operations happen as follows:

result = 0

result ^= 4
result = 4

result ^= 2
result = 6

result ^= 7
result = 1

result ^= 2
result = 3

result ^= 4
result = 7

Final result:

7

Notice how both occurrences of 4 and 2 cancel each other, leaving only 7.

Real-Life Analogy

Imagine a drawer containing pairs of socks, except for one sock that has no matching pair. If every matching pair magically disappeared whenever both socks were found, only the unmatched sock would remain. The XOR operation behaves exactly the same way for numbers.

Best Practices

• Use the HashMap solution when finding all elements that appear exactly once.
• Use the XOR trick only when the problem guarantees that every other element appears exactly twice.
• Always clarify whether the requirement is for unique elements or distinct elements.
• Java Streams provide a concise alternative when you're already using functional programming.

Common Mistakes

1. Confusing unique elements with distinct elements.
2. Applying the XOR solution when elements appear more than twice.
3. Using the XOR trick when multiple unique elements exist.
4. Building a frequency map without using getOrDefault(), resulting in unnecessarily complex code.

Expert Tips

• The XOR trick is commonly extended into another interview problem where two unique elements must be found using bit manipulation.
• Mentioning the assumptions required for the XOR solution demonstrates strong analytical skills during interviews.
• For strings or custom objects, use the HashMap frequency approach because XOR only works with integer values.

Comparison Table

Frequently Asked Questions

What is the difference between unique and distinct elements?

Unique elements appear exactly once, whereas distinct elements include every different value regardless of frequency.

When can I use the XOR trick?

Only when every element appears exactly twice except for one unique element.

Can the XOR trick find multiple unique elements?

No. It is designed for exactly one unique element. Finding two unique elements requires a different bit manipulation technique.

What is the best general solution for finding unique elements?

Using a HashMap to count frequencies and then selecting elements whose frequency equals one.

Does the output order matter?

If insertion order is important, use a LinkedHashMap instead of a regular HashMap.

Is finding unique elements the same as finding the majority element?

No. A majority element appears more than n/2 times, whereas a unique element appears exactly once.

Can this approach be used with strings or custom objects?

Yes. The HashMap approach works with any type that correctly implements equals() and hashCode().

What is the time complexity of the HashMap solution?

The overall complexity is O(n) because one pass builds the frequency map and another pass identifies the unique elements.