Find All Elements Appearing Once in an Array

Title: Find All Elements Appearing Once in an Array

Picking out the values that show up only once in a noisy array is a skill that comes up constantly in interviews, from warm-up questions all the way to the setup for harder duplicate-detection problems. In this guide, you will learn how to collect every value that occurs exactly once in an array of arbitrary integers, write a complete Java implementation around a frequency map, trace the algorithm one iteration at a time, and sharpen your intuition with worked examples, common mistakes, and the follow-up questions interviewers like to drill into.

Understanding the Problem

You are given an integer array nums whose elements can repeat any number of times and are not restricted to any particular range. Return a list of every value that appears exactly once, that is, neither zero, two, nor three or more times.

For instance, if nums = {4, 3, 4, 2, 2, 7, 8, 8}, the values 4, 2, and 8 each occur twice, while 3 and 7 occur exactly once, so the answer is [3, 7]. The order of the returned list does not have to match any particular convention; most interviewers accept any permutation of the correct values.

Unlike problems that constrain every value to the range [1, n], this array can contain negative numbers, large numbers, or any mix of repeats. That rules out index-based tricks and points directly at counting with a hash-based frequency map.

Approach Using a Frequency Map

The idea is to count how many times each value occurs, then make a second pass over those counts and keep only the values whose count is exactly 1. A Map<Integer, Integer> that maps each value to its running count is the natural structure for the first pass, and a simple filter handles the second.

Here are the steps:

1. Create an empty Map<Integer, Integer> called frequency. Use a LinkedHashMap so the eventual output preserves first-appearance order.
2. Iterate every value num in nums.
3. Update the count with frequency.put(num, frequency.getOrDefault(num, 0) + 1), which safely defaults a first-time value to 0 before incrementing.
4. Once every element has been counted, create an empty List<Integer> called result.
5. Iterate the entries of frequency.
6. If an entry’s value (the count) equals exactly 1, add its key (the number) to result.
7. Return result after the second pass finishes.

Java Program to Find All Elements Appearing Once

Let us put the approach into a complete, compilable Java program:

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class FindElementsAppearingOnce {

    public static List<Integer> findElementsAppearingOnce(int[] nums) {
        Map<Integer, Integer> frequency = new LinkedHashMap<>();
        for (int num : nums) {
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }

        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
            if (entry.getValue() == 1) {
                result.add(entry.getKey());
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 4, 2, 2, 7, 8, 8};
        List<Integer> singles = findElementsAppearingOnce(nums);
        System.out.println("Elements appearing exactly once: " + singles);
    }
}

Explanation of the Program

• The method findElementsAppearingOnce accepts an int[] and returns a List<Integer> holding every value whose total count is exactly one.
• frequency is declared as a LinkedHashMap rather than a plain HashMap so the entries come back out in the order their keys were first inserted, which keeps the output order predictable across runs.
• frequency.getOrDefault(num, 0) + 1 is what makes the counting loop safe. Reading a key that has never been inserted returns 0 instead of null, so the very first sighting of a value correctly becomes a count of 1.
• The counting loop runs to completion before anything is filtered. That ordering matters: a value is only truly a ‘single’ once every occurrence in the array has been tallied, since a later repeat could still turn a count of one into two or more.
• The second loop walks frequency.entrySet() and checks entry.getValue() == 1. Only keys whose final count matches that exact value are copied into result.
• main calls the method on a sample input and prints the result. The sample mixes three repeated values with two unique ones so the filter has real work to do.

Step-by-Step Trace

Let us walk the counting loop through a small fresh input so the exact-count filter is easy to follow. Consider nums = {9, 5, 9, 1, 5, 6, 3} with length 7; frequency starts empty.

At the end of iteration i, frequency holds the exact count of every value seen in nums[0..i], no more and no less. Notice that 9 and 5 both climb to a count of 2 during the walk; because the filter only runs after counting finishes, the final result correctly reports [1, 6, 3], in the order those values first appeared, and leaves 9 and 5 out.

Examples

Let us look at a few runs that stretch different parts of the algorithm.

Example 1: A Mix of Singles and Pairs

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class FindElementsAppearingOnce {

    public static List<Integer> findElementsAppearingOnce(int[] nums) {
        Map<Integer, Integer> frequency = new LinkedHashMap<>();
        for (int num : nums) {
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }

        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
            if (entry.getValue() == 1) {
                result.add(entry.getKey());
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 4, 2, 2, 7, 8, 8};
        List<Integer> singles = findElementsAppearingOnce(nums);
        System.out.println("Elements appearing exactly once: " + singles);
    }
}

The array has eight elements. 3 and 7 each appear once, while 4, 2, and 8 each appear twice. The method returns [3, 7], the order matching how those values first appeared in nums.

Example 2: Every Value is Distinct

int[] nums = {10, 20, 30};
List<Integer> singles = findElementsAppearingOnce(nums);

System.out.println("Singles: " + singles);
// Output: Singles: [10, 20, 30]

No value repeats, so every count in frequency stops at 1 and the filter accepts every key. The returned list equals the full set of input values, which is the expected answer when an array has no duplicates at all.

Example 3: Every Value Repeats

int[] nums = {5, 5, 5, 5};
List<Integer> singles = findElementsAppearingOnce(nums);

System.out.println("Singles: " + singles);
// Output: Singles: []

5 appears four times and nothing else is present. Since no key ever reaches a count of exactly 1, the filter matches nothing and the result is an empty list.

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing exact-count filtering:

• Checking count > 0 instead of == 1 – every key already present in frequency has a count of at least one, so a > 0 check wrongly returns every distinct value, not just the ones that occur a single time. Compare entry.getValue() to exactly 1.
• Deciding inclusion during the counting loop – adding a key to result the moment its count is 1 ignores later repeats of the same value. 9 would wrongly appear even though it climbs to 2 later in the array. Count every element first, then filter the finished map in a separate pass.
• Assuming an XOR trick always applies – XOR-based tricks that isolate a single odd-one-out value only work for the special case where exactly one value appears once and every other value appears exactly twice. Applying XOR on an array with multiple singles or with values that repeat three or more times produces a meaningless number.
• Forgetting the default count – calling frequency.get(num) + 1 on a value seen for the first time throws a NullPointerException because there is no boxed Integer to unbox. Use frequency.getOrDefault(num, 0) + 1 so a missing key defaults to zero.
• Assuming HashMap preserves insertion order – printing frequency.keySet() from a plain HashMap can print values in a different order on different runs, which breaks tests that assert on list order. Use LinkedHashMap when the output order should match first appearance.

Additional Considerations

A few points worth remembering about this algorithm:

1. Time complexity: Counting is one O(n) pass and filtering the map is another pass bounded by the number of distinct values, which is at most n. The overall running time is O(n).
2. Space complexity: frequency can hold up to n distinct keys in the worst case, where every value in nums is unique, so the extra space is O(n).
3. Order guarantee: LinkedHashMap returns entries in first-insertion order, which makes the output deterministic. A plain HashMap works just as correctly if the caller truly does not care about order.
4. Why the value range does not matter here: unlike index-based duplicate tricks, a hash map treats every int, including negative numbers and Integer.MIN_VALUE or Integer.MAX_VALUE, as just another key.
5. A constrained special case: if the problem guarantees that exactly one value appears once and every other value appears exactly twice, XOR-ing every element together cancels the paired values and leaves the single value behind in O(1) extra space, which is faster than building a map but only valid under that exact guarantee.

Edge Cases to Test

Before you declare the implementation done, run it against these boundary inputs:

• Empty array
• Single-element array
• All elements identical (no singles at all)
• All elements distinct (every value is a single)
• A value appearing more than twice
• Negative numbers present
• Integer.MIN_VALUE / Integer.MAX_VALUE present
• Null array reference

Interview Follow-up Questions

Once the base version works, an interviewer will usually probe deeper with questions like these:

• What if the array is already sorted? – a single pass comparing each element to its neighbors replaces the hash map entirely, since a single’s two neighbors can never equal it; this drops the extra space to O(1) beyond the output list.
• What if the array is guaranteed to have exactly one single value and every other value appears exactly twice? – XOR every element together; paired values cancel to zero and only the single remains, giving O(n) time and O(1) space.
• What if you need elements that repeat instead of elements that appear exactly once? – invert the filter to entry.getValue() > 1; every other part of the algorithm stays the same.
• What if the input arrives as a stream of unknown length? – maintain the frequency map incrementally as elements arrive; a value can only be confirmed as a true single once the stream ends, since a later occurrence could still turn it into a pair.
• How would you handle billions of entries that will not fit in memory? – partition the stream into buckets by hash range, count each partition independently on a worker, then merge the per-partition frequency maps before applying the == 1 filter; an approximate alternative uses a count-min sketch when exact counts are not required.

Conclusion

In this guide, we solved the problem of finding every value in an array that appears exactly once. A frequency map built with getOrDefault handles the counting in a single pass, and a second pass that checks entry.getValue() == 1 is what correctly separates values that occur a single time from values that repeat. That two-pass shape, count everything first, then filter precisely, is a pattern worth recognizing across many exact-count interview problems.

Try adapting the code to accept an arbitrary target count, emit results incrementally from a stream, or swap in the XOR trick when the problem guarantees exactly one single value among pairs. Happy coding!

You can learn more about Array techniques: Arrays