First Non-Repeating Value

Find the first input value whose final frequency is one.

Algorithm

Canonical input [3, 5, 2, 5, 3, 8, 2] prints 8. The replay uses the same input in every language, so this Java DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

Basic.java

import java.util.*;

public class Basic {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 5, 3, 8, 2};
        Map<Integer, Integer> count = new LinkedHashMap<>();
        for (int value : arr) {
            count.put(value, count.getOrDefault(value, 0) + 1);
        }
        for (int value : arr) {
            if (count.get(value) == 1) {
                System.out.println(value);
                break;
            }
        }
    }
}

Complexity

Time: O(n) average
Space: O(k) for k distinct values

Implementation notes

Keep output formatting deterministic. Do not rely on unordered hash-map printing when the lesson needs cross-language comparison.
The trace highlights the hash table state after each write.

two-pass lookup The first pass builds a frequency table. The second pass keeps the original order and stops at the first value with frequency one.