First Non-Repeating Integer in an Array

Given an array of integers, return the first element (from the left) that appears exactly once in the array. Return OptionalInt.empty() if every element repeats. (OptionalInt is a container that holds either one int or nothing.)

Example 1

Text

Input:  [9, 2, 3, 2, 6, 6]
Output: 9
Explanation: 9 and 3 appear once. 9 comes first.

Example 2

Text

Input:  [4, 5, 1, 2, 0, 4]
Output: 5
Explanation: 4 appears twice, so the first unique value is 5.

Example 3

Text

Input:  [1, 1, 2, 2]
Output: empty

Brute force: compare each element with all the others

For each position i, check whether any other position holds the same value. The first element with no match is the answer.

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt firstUnique(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean repeated = false;
            for (int j = 0; j < nums.length; j++) {
                if (i != j && nums[i] == nums[j]) {
                    repeated = true;
                    break;
                }
            }
            if (!repeated) {
                return OptionalInt.of(nums[i]);
            }
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(firstUnique(new int[]{9, 2, 3, 2, 6, 6}));
        System.out.println(firstUnique(new int[]{4, 5, 1, 2, 0, 4}));
        System.out.println(firstUnique(new int[]{1, 1, 2, 2}));
    }
}

Output

OptionalInt[9]
OptionalInt[5]
OptionalInt.empty

Time: O(n²). Space: O(1).

Optimal: count, then scan the input again

Two passes:

Count how many times each value appears, using a HashMap<Integer, Integer>. A HashMap stores key-value pairs and finds a key in O(1) expected time.
Walk the input from left to right and return the first value whose count is 1.

Walkthrough with [4, 5, 1, 2, 0, 4]:

After pass 1, the counts are {4: 2, 5: 1, 1: 1, 2: 1, 0: 1}.

pass 2 element	count	result
4	2	keep going
5	1	return 5

Java

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

public class Main {
    static OptionalInt firstUnique(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int x : nums) {
            counts.merge(x, 1, Integer::sum);
        }
        for (int x : nums) {
            if (counts.get(x) == 1) {
                return OptionalInt.of(x);
            }
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(firstUnique(new int[]{9, 2, 3, 2, 6, 6}));
        System.out.println(firstUnique(new int[]{4, 5, 1, 2, 0, 4}));
        System.out.println(firstUnique(new int[]{1, 1, 2, 2}));
    }
}

Output

OptionalInt[9]
OptionalInt[5]
OptionalInt.empty

Time: O(n): two passes, each doing O(1) expected map work per element. Space: O(n) for the map, in the worst case where all values are distinct.

counts.merge(x, 1, Integer::sum) stores 1 when x is new and otherwise stores the sum of the old count and 1. counts.get(x) returns null when x is not a key, and unboxing null throws NullPointerException. Here every x comes from nums, so the key is always present. counts.get(x) == 1 compares an Integer with an int, so Java unboxes the count and compares values.

Why the second pass walks the input, not the map

A HashMap has no defined iteration order. This is wrong:

Java

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

public class Main {
    public static void main(String[] args) {
        int[] nums = {9, 2, 3, 2, 6, 6};
        Map<Integer, Integer> counts = new HashMap<>();
        for (int x : nums) {
            counts.merge(x, 1, Integer::sum);
        }
        // Wrong: returns *some* unique value, which may be 3 instead of 9.
        boolean foundAny = false;
        for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
            if (e.getValue() == 1) {
                foundAny = true;
                break;
            }
        }
        System.out.println("found a unique value: " + foundAny);
    }
}

Output

found a unique value: true

The input array keeps the original order, so the second pass has to walk it. A LinkedHashMap also works for the second pass, because it iterates in insertion order.

Edge cases

Empty array: OptionalInt.empty().
Single element: that element.
Values are small and non-negative (for example 0..=1000): an int[] of counts indexed by value is faster than a HashMap.