First Non-Repeating Integer (Hashing)

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

This is the hashing version of First Non-Repeating Integer.

Example 1

Text

Input:  [2, 54, 7, 2, 6, 54]
Output: 7
Explanation: 2 and 54 appear twice. 7 is the first value that appears once.

Example 2

Text

Input:  [3, 3]
Output: empty

Brute force: count each element by scanning

For each element, count its occurrences with a full scan. Return the first element whose count is 1.

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt firstUnique(int[] nums) {
        for (int x : nums) {
            int count = 0;
            for (int y : nums) {
                if (y == x) count++;
            }
            if (count == 1) return OptionalInt.of(x);
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(firstUnique(new int[]{2, 54, 7, 2, 6, 54}) + " " + firstUnique(new int[]{3, 3}));
    }
}

Output

OptionalInt[7] OptionalInt.empty

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

Optimal: a HashMap of counts, then a second pass

Count every value in one pass, using merge(x, 1, Integer::sum), which adds 1 to the count of x or stores 1 when x is absent.
Walk the original array and return the first value with a count of 1.

Walkthrough with [2, 54, 7, 2, 6, 54]:

Pass 1 gives the counts {2: 2, 54: 2, 7: 1, 6: 1}.

pass 2 value	count	result
2	2	continue
54	2	continue
7	1	return 7

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<>(nums.length * 2);
        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[]{2, 54, 7, 2, 6, 54}) + " " + firstUnique(new int[]{3, 3}));
        System.out.println(firstUnique(new int[]{4, 5, 1, 2, 0, 4}));
    }
}

Output

OptionalInt[7] OptionalInt.empty
OptionalInt[5]

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

The second pass has to walk nums, not the map. A HashMap's iteration order is unspecified, so "the first entry with count 1" in the map isn't necessarily the first in the input.

Single pass over the input, then a pass over the map

If the input is a stream you can read only once, store each value's count and its first position, as a two-element int[]. Then pick the unique value with the smallest position from the map. The map is walked in an unspecified order, but the smallest first position is unique, so the answer does not depend on that order:

Java

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

public class Main {
    static OptionalInt firstUnique(Iterable<Integer> nums) {
        Map<Integer, int[]> info = new HashMap<>(); // value -> {count, first index}
        int i = 0;
        for (int x : nums) {
            info.computeIfAbsent(x, k -> new int[]{0, 0})[0]++;
            if (info.get(x)[0] == 1) info.get(x)[1] = i;
            i++;
        }
        int bestValue = 0;
        int bestIndex = Integer.MAX_VALUE;
        for (Map.Entry<Integer, int[]> e : info.entrySet()) {
            int[] v = e.getValue();
            if (v[0] == 1 && v[1] < bestIndex) {
                bestIndex = v[1];
                bestValue = e.getKey();
            }
        }
        return bestIndex == Integer.MAX_VALUE ? OptionalInt.empty() : OptionalInt.of(bestValue);
    }

    public static void main(String[] args) {
        System.out.println(firstUnique(List.of(2, 54, 7, 2, 6, 54)));
    }
}

Output

OptionalInt[7]

Time: O(n). Space: O(n). The second pass runs over the distinct values instead of the input.

Edge cases

Empty input: OptionalInt.empty().
One element: that element.
All elements distinct: the first element.