The first unique
element

"First superstar without a body double" = first value with frequency 1

Behind the story is a plain array problem: find the first element whose frequency in the entire array is exactly one, or return -1 if none exists. For A = [9, 6, 7, 6], the counts are 9→1, 6→2, 7→1. Both 9 and 7 are unique, but 9 arrives first — so the answer is 9.

The future can invalidate the present

A tempting idea: track "seen" values and return the first one that looks new. It fails. In [9, 6, 7, 9], index 0 looks unique — until a second 9 shows up at the end. You genuinely cannot declare any element unique until you've counted the whole array.

The brute-force fix — re-scan the array to count each element as you reach it — is O(N) per element, so O(N²) overall. With N up to 100,000 that's too slow, and it repeats the same counting work over and over. Count once, store the totals, and look them up instantly. That's a frequency map.

Split global counting from ordered scanning

This is the clean idea at the center of the solution: don't force one structure to answer both questions. Use a map for the counts, and reuse the original array for the order.

Build the counts, then scan in order

Pick an input and step through. Pass 1 (amber) sweeps the array building the frequency map — pills turn teal at count 1, terracotta when they climb higher. Pass 2 (blue) re-scans left to right and stops at the first value whose count is 1.

Count, then find the first one

# pass 1 — global counts
for value in array:
    freq[value] += 1

# pass 2 — respect arrival order
for value in array:
    if freq[value] == 1:
        return value

return -1

Why the second pass is non-negotiable

Take A = [4, 9, 7, 4]. After pass 1: 4→2, 9→1, 7→1. Two uniques exist — but the answer must be 9, because it appears before 7. Iterating the map instead of the array could return either, in any order. Only a left-to-right scan of the original array respects arrival:

Clean Java with a HashMap

import java.util.*;

static int firstUnique(int[] arr) {
    Map<Integer,Integer> freq = new HashMap<>();

    // pass 1: count every value
    for (int v : arr)
        freq.put(v, freq.getOrDefault(v, 0) + 1);

    // pass 2: first value with count 1, in original order
    for (int v : arr)
        if (freq.get(v) == 1) return v;

    return -1;
}

getOrDefault(v, 0) + 1 treats a missing key as 0, so the first sighting becomes 1 and every repeat increments — no containsKey branch needed. Both passes are O(N) with O(1) average map operations: O(N) time, O(N) space, which is optimal since you must read every element at least once.

Why not XOR, sorting, or a single set?

A LinkedHashMap would preserve insertion order and works too — but when the input array already holds the order you need, reuse it instead of adding a structure just to remember it.

Global preprocessing, then an ordered scan

This is a template, not a one-off. Whenever a problem asks for the first / earliest / leftmost element satisfying a condition that depends on the whole input, split it into two phases:

The same shape solves the first non-repeating character in a string, the first element occurring exactly K times, and more. Note the contrast with the sliding-window distinct-count problem: there the frequency map was local to a moving window; here it's global across the array. A HashMap is just a value→count tool — the algorithm is defined by how that information changes.

Reconstruct it, don't memorize it

1. I need the first element that appears exactly once.
2. "Exactly once" is a frequency condition → I need total counts.
3. Values reach 10⁹, so a giant array is out → use a HashMap.
4. "First" means order matters → the array already holds it.
5. Pass 1 counts; pass 2 scans the array for the first count of 1.
6. If none qualifies, return −1.