Find All Elements that Appear Exactly Twice

Title: Find All Elements that Appear Exactly Twice

Counting how often each value shows up in an array is one of the most common building blocks in coding interviews, and the exact-count variant trips up candidates who stop at ‘has this value been seen before’. In this guide, you will learn how to collect every value that appears exactly twice 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 twice, that is, neither once nor three or more times.

For instance, if nums = {5, 3, 8, 3, 5, 9, 8, 1}, every one of 5, 3, and 8 occurs exactly twice, while 9 and 1 occur once, so the answer is [5, 3, 8]. 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 2. 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 2, add its key (the number) to result.
7. Return result after the second pass finishes.

Java Program to Find All Elements that Appear Exactly Twice

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 FindElementsAppearingTwice {

    public static List<Integer> findElementsAppearingTwice(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() == 2) {
                result.add(entry.getKey());
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {5, 3, 8, 3, 5, 9, 8, 1};
        List<Integer> twice = findElementsAppearingTwice(nums);
        System.out.println("Elements appearing exactly twice: " + twice);
    }
}

Explanation of the Program

• The method findElementsAppearingTwice accepts an int[] and returns a List<Integer> holding every value whose total count is exactly two.
• 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 ‘exactly twice’ once every occurrence in the array has been tallied.
• The second loop walks frequency.entrySet() and checks entry.getValue() == 2. 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 = {2, 4, 2, 6, 4, 4, 7} 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 4 reaches a count of 2 at iteration 5 but climbs to 3 by iteration 6; because the filter only runs after counting finishes, the final result correctly reports [2] and leaves 4 out.

Examples

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

Example 1: A Mix of Singles, Pairs, and a Fresh Value

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

public class FindElementsAppearingTwice {

    public static List<Integer> findElementsAppearingTwice(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() == 2) {
                result.add(entry.getKey());
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {5, 3, 8, 3, 5, 9, 8, 1};
        List<Integer> twice = findElementsAppearingTwice(nums);
        System.out.println("Elements appearing exactly twice: " + twice);
    }
}

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

Example 2: Every Value is Distinct

int[] nums = {10, 20, 30, 40};
List<Integer> twice = findElementsAppearingTwice(nums);

System.out.println("Twice: " + twice);
// Output: Twice: []

No value repeats, so every count in frequency stops at 1 and the filter finds nothing. The returned list is empty, which is the expected answer when an array has no duplicates at all.

Example 3: A Value Appears Three Times

int[] nums = {6, 6, 6, 2, 2, 9};
List<Integer> twice = findElementsAppearingTwice(nums);

System.out.println("Twice: " + twice);
// Output: Twice: [2]

6 appears three times and 2 appears twice. Even though 6 repeats more often than 2, ‘exactly twice’ excludes it; only 2 satisfies entry.getValue() == 2, so the result is [2].

Common Mistakes to Avoid

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

• 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.
• Filtering with >= 2 instead of == 2 – a value that appears three or more times, like 4 in {2, 4, 2, 6, 4, 4, 7}, sneaks into the result if the check accepts ‘at least twice’. Compare entry.getValue() to exactly 2.
• Deciding inclusion during the counting loop – adding a key to result the moment its count first reaches 2 ignores later increments. 4 would wrongly appear even though it climbs to 3 by the end. Count every element first, then filter the finished map in a separate pass.
• 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.
• Reusing an index-based duplicate trick – sign-flipping tricks that work on arrays bounded to [1, n] assume every value is a valid array index. Applying that approach here on arbitrary integers, including negative numbers, throws ArrayIndexOutOfBoundsException. A hash-based frequency count has no such restriction.

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. Alternative with a bounded range: if every value is known to fall within a small range, a plain int[] counts array avoids the boxing overhead of a Map<Integer, Integer> and can count slightly faster, at the cost of generality.

Edge Cases to Test

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

• Empty array
• Single-element array
• All elements identical (one value appearing many times)
• All elements distinct (empty result)
• 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 you need elements appearing at least twice instead of exactly twice? – relax the filter from == 2 to >= 2; every other part of the algorithm stays the same.
• What if you need elements appearing exactly K times for an arbitrary K? – generalize the filter to entry.getValue() == k, where k is passed in as a parameter alongside nums.
• What if the array is already sorted? – a single pass with a sliding count of consecutive equal values replaces the hash map entirely, dropping the extra space to O(1) beyond the output list.
• What if the input arrives as a stream of unknown length? – maintain the frequency map incrementally as elements arrive; emit a value the moment its count transitions from 1 to 2, and retract it if the count later transitions from 2 to 3, since a streaming context cannot look back once elements are gone.
• 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; 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 twice. A frequency map built with getOrDefault handles the counting in a single pass, and a second pass that checks entry.getValue() == 2 is what correctly separates values that occur twice from values that occur once or three or more times. 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 a plain array based counter when the input range is bounded. Happy coding!

You can learn more about Array techniques: Arrays