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

Java keeps the input as a primitive int[], while the frequency table is declared as Map<Integer, Integer> and backed by new LinkedHashMap<>(). Keys and counts are boxed through Integer.valueOf, so these small fixture values may use cached Integer instances inside the generic map.
The first pass uses count.getOrDefault(value, 0) + 1 followed by count.put(value, ...), so repeated values replace the mapped count value and first sightings insert new keys. LinkedHashMap keeps insertion order stable for the replayed table display.
The first non-repeating result is determined by scanning the original array again, not by iterating the map. count.get(value) == 1 finds value 8 at arr[5], preserving first-occurrence order from the array.
Integer hashing and equality are value-based for these keys; collision and resize behavior stay below the replay. Allocation is mainly the LinkedHashMap entries plus any uncached boxed integers, all managed by JVM GC.

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.