Find the First Non-Repeating Element in an Array

Title: Find the First Non-Repeating Element in an Array

In this guide, you’ll learn how to find the first element in an integer array that does not repeat anywhere else in the array. This is a classic warm-up for coding interviews that teaches a durable pattern: count once with a hash map, then scan once more in original order to pick the winner.

The problem looks tiny, but it quietly rewards good habits around frequency counting, two-pass algorithms, and the Java Collections framework. Let’s explore a clean O(n) solution and the ideas that let you adapt it to characters, streams, and larger follow-up questions.

Understanding the Problem

Given an array of integers such as {4, 5, 1, 2, 0, 4, 2, 5}, return the first element that occurs exactly once. For this input, 4 and 5 both repeat, so the answer is 1. If every element repeats, we return a sentinel like -1 or throw an exception, depending on what callers expect.

The word “first” matters: it refers to original array order, not the smallest numeric value or an alphabetical rank. A HashMap is a natural fit for counting, but we must walk the array itself a second time to recover insertion order, because HashMap gives no ordering guarantees on its own.

Approach and Algorithm Steps

The idea is a textbook two-pass algorithm. The first pass gathers the information we need, and the second pass turns that information into the answer while preserving order.

1. Validate the input and reject a null or empty array with an IllegalArgumentException.
2. Create a HashMap<Integer, Integer> named counts to track how many times each value appears.
3. Make the first pass: iterate the array and increment the count for each element using getOrDefault.
4. Make the second pass: iterate the array again from index 0, following original order.
5. For each element, look up its count in counts and check whether it equals 1.
6. If the count is 1, return that element immediately, because scanning in order means the first match wins.
7. If the second pass completes without a hit, return -1 to signal that every element repeats.

Java Program

Below is a full, compilable program. The method findFirstNonRepeating encapsulates the algorithm, and main wires up a sample input and prints a readable result.

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

public class FirstNonRepeatingElement {

    public static int findFirstNonRepeating(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("Array must not be empty");
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (int value : numbers) {
            counts.put(value, counts.getOrDefault(value, 0) + 1);
        }
        for (int value : numbers) {
            if (counts.get(value) == 1) {
                return value;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] numbers = {4, 5, 1, 2, 0, 4, 2, 5};
        int result = findFirstNonRepeating(numbers);
        if (result == -1) {
            System.out.println("No non-repeating element found");
        } else {
            System.out.println("First non-repeating element: " + result);
        }
    }
}

Explanation of the Program

The imports pull in HashMap and Map so the local variable can be typed to the interface while the implementation stays a HashMap. Programming against the interface keeps the method flexible if we later swap in a LinkedHashMap or a TreeMap.

The method findFirstNonRepeating accepts int[] numbers and returns an int. The early guard throws when the input is null or has length 0. Validating at the boundary keeps the rest of the method focused on the happy path.

The first for loop performs the counting pass. The idiom counts.getOrDefault(value, 0) + 1 reads as “take the current count for value, defaulting to zero, then add one”. It avoids the ugly null check that counts.get(value) would otherwise require.

The second for loop iterates the original array, not the map. This is the critical detail that preserves original order. The first value whose stored count is exactly 1 is returned immediately. If the loop finishes without a hit, the method returns -1.

The main method defines a sample input, calls the helper, and prints a message tailored to whether a non-repeating element was found. Keeping the printing in main and the logic in the helper is a small but useful habit for testability.

Step-by-Step Trace

Walk through the input {7, 3, 7, 9, 3, 11}. After the first pass, counts holds {7=2, 3=2, 9=1, 11=1}. The table below shows the second pass, which is where the answer is actually produced.

At the end of each iteration i of the second pass, every value in numbers[0..i-1] has been confirmed to repeat somewhere in the array, and the first index where counts.get(numbers[i]) equals 1 is the answer. The invariant is simple, which is why the two-pass structure is so dependable.

Examples

Example 1: Mix of repeats and uniques

A typical input where some values repeat and some do not. The first non-repeating element is 1, because 4 and 5 both appear twice.

int[] input = {4, 5, 1, 2, 0, 4, 2, 5};
// Output: 1

Example 2: Every element repeats

When no element is unique, the method returns the sentinel -1. Callers must handle this value explicitly, because -1 is also a legitimate array element in other inputs.

int[] input = {2, 2, 3, 3, 4, 4};
// Output: -1

Example 3: All elements are distinct

When every value is unique, the answer is simply numbers[0]. The second pass short-circuits on the very first iteration.

int[] input = {10, 20, 30};
// Output: 10

Common Mistakes to Avoid

A handful of specific slips come up repeatedly on this problem. Spotting them in your own code before an interviewer does is the quickest way to look practiced.

• Iterating the map instead of the array – HashMap provides no insertion-order guarantee, so iterating it may return a value that is non-repeating but not the first non-repeating. Always walk the original numbers array in the second pass.
• Returning the count rather than the value – writing return counts.get(value) prints 1 for every valid input and silently hides the bug. Return the array element, not its frequency.
• Comparing boxed Integers with == – counts.get(value) returns an Integer; comparing two Integer objects with == compares references outside the -128..127 cache range. Rely on auto-unboxing against the primitive literal 1, or call .equals(1).
• Using 0 as the not-found sentinel – 0 is a perfectly valid array value and will mask real answers. Prefer -1 only when it cannot appear in your input domain; otherwise throw a dedicated exception.
• Confusing non-repeating with first-seen – the “first element that has not yet been seen” is just numbers[0] and is a different problem. Read the prompt carefully before coding.

Edge Cases to Test

A short checklist of boundary inputs. Walking these aloud in an interview, unprompted, is a reliable way to signal engineering maturity.

• Empty array
• Single-element array
• All identical elements
• All distinct elements
• Non-repeating element at index 0
• Non-repeating element at the last index
• Negative values mixed with positives
• Integer.MIN_VALUE / Integer.MAX_VALUE present
• Null array reference

Additional Considerations

Time complexity is O(n). Each pass visits every element once, and HashMap operations are amortized O(1). The two linear passes compose to a single O(n) total, which is optimal for this problem because every element must be inspected at least once.

Space complexity is O(k), where k is the number of distinct values in the input. In the worst case, every element is unique and k equals n, so the map grows to O(n). The returned int itself takes constant space.

A memory-order trade-off is worth knowing: using a LinkedHashMap instead of a HashMap removes the need for the second array pass, because LinkedHashMap preserves insertion order on its keys. The constant factor is slightly higher per operation, but the code becomes a single pass over the map at the end. For characters restricted to ASCII, swapping the HashMap for an int[128] array drops lookups to true O(1) with far less memory overhead and no hashing cost.

The counting pass is embarrassingly parallel: partition the array, build a local count per partition, and merge the partial maps. This matters more for large arrays than it looks here, because the shared second pass still needs the merged counts before it can short-circuit.

Interview Follow-up Questions

Real interviews rarely stop at the base problem. The variations below are the ones a sharp interviewer tends to ask, roughly in order of difficulty.

• What if the elements are characters instead of integers? – swap the HashMap for a fixed-size int[26] for lowercase letters or int[128] for ASCII; lookups become true O(1) and the memory footprint shrinks dramatically.
• What if the input is a stream of unknown length and you must answer online? – maintain a LinkedHashMap<Integer, Integer>; after every update, the first entry whose count is 1 is the current answer, so each new element is O(1) amortized.
• What if you need the k-th non-repeating element rather than the first? – keep the second pass but increment a running counter each time counts.get(value) == 1; return the k-th hit, or signal that fewer than k exist.
• What if the array is immutable and extra memory is capped at O(1)? – sort a copy in O(n log n) and sweep for runs of length 1; without even a copy, you must trade more time (nested loops at O(n^2)) for the memory bound.
• What if the data lives on disk and does not fit in memory? – external sort by value, then stream through the runs, breaking ties by original index; record each value’s first-seen index during the counting phase for the final comparison.

Conclusion

You now have a dependable template for counting-and-selecting problems: pass once to tally, pass again to pick. The same shape solves “first repeating element”, “character frequency”, and many string-anagram questions with only small adjustments to the condition in the second pass.

Try adapting the code for String inputs, for streams, and for the k-th variant. Each tweak surfaces a different corner of Java’s collections and sharpens your intuition for when to reach for a HashMap, a LinkedHashMap, or a plain array. You can learn more Array problems and patterns here: https://dailyjavaconcept.com/category/arrays/.