Hash Tables

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.

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.

Basic Implementation

Basic.java
Replay: real traced execution (multi-file project)
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;
            }
        }
    }
}

  1. arr ← [3, 5, 2, 5, 3, 8, 2]

    1import java.util.*;
    values this step[3, 5, 2, 5, 3, 8, 2]arr

  2. count ← {}

    5int[] arr = {3, 5, 2, 5, 3, 8, 2};6Map<Integer, Integer> count = new LinkedHashMap<>();7for (int value : arr) {
    values this step{}count

  3. count ← {3: 1}

    5int[] arr = {3, 5, 2, 5, 3, 8, 2};6Map<Integer, Integer> count = new LinkedHashMap<>();7for (int value : arr) {
    values this step{} → {3: 1}count3value

  4. count ← {3: 1, 5: 1}

    5int[] arr = {3, 5, 2, 5, 3, 8, 2};6Map<Integer, Integer> count = new LinkedHashMap<>();7for (int value : arr) {
    values this step{3: 1} → {3: 1, 5: 1}count5value

  5. count ← {3: 1, 5: 1, 2: 1}

    5int[] arr = {3, 5, 2, 5, 3, 8, 2};6Map<Integer, Integer> count = new LinkedHashMap<>();7for (int value : arr) {
    values this step{3: 1, 5: 1} → {3: 1, 5: 1, 2: 1}count2value

  6. count ← {3: 1, 5: 2, 2: 1}

    5int[] arr = {3, 5, 2, 5, 3, 8, 2};6Map<Integer, Integer> count = new LinkedHashMap<>();7for (int value : arr) {
    values this step{3: 1, 5: 1, 2: 1} → {3: 1, 5: 2, 2: 1}count5value

  7. count ← {3: 2, 5: 2, 2: 1}

    5int[] arr = {3, 5, 2, 5, 3, 8, 2};6Map<Integer, Integer> count = new LinkedHashMap<>();7for (int value : arr) {
    values this step{3: 1, 5: 2, 2: 1} → {3: 2, 5: 2, 2: 1}count3value

  8. count ← {3: 2, 5: 2, 2: 1, 8: 1}

    5int[] arr = {3, 5, 2, 5, 3, 8, 2};6Map<Integer, Integer> count = new LinkedHashMap<>();7for (int value : arr) {
    values this step{3: 2, 5: 2, 2: 1} → {3: 2, 5: 2, 2: 1, 8: 1}count8value

  9. count ← {3: 2, 5: 2, 2: 2, 8: 1}

    5int[] arr = {3, 5, 2, 5, 3, 8, 2};6Map<Integer, Integer> count = new LinkedHashMap<>();7for (int value : arr) {
    values this step{3: 2, 5: 2, 2: 1, 8: 1} → {3: 2, 5: 2, 2: 2, 8: 1}count2value

  10. i ← 0, value ← 3, count[value] ← 2, found ← no

    1import java.util.*;
    values this step0i3value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  11. i ← 1, value ← 5, count[value] ← 2, found ← no

    1import java.util.*;
    values this step1i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  12. i ← 2, value ← 2, count[value] ← 2, found ← no

    1import java.util.*;
    values this step2i2value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  13. i ← 3, value ← 5, count[value] ← 2, found ← no

    1import java.util.*;
    values this step3i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  14. i ← 4, value ← 3, count[value] ← 2, found ← no

    1import java.util.*;
    values this step4i3value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  15. i ← 5, value ← 8, count[value] ← 1, found ← yes, result ← 8

    1import java.util.*;
    values this step5i8value1count[value]yesfound8result{3: 2, 5: 2, 2: 2, 8: 1}count

  16. stdout ← 8

    11if (count.get(value) == 1) {12    System.out.println(value);13    break;
    values this step8stdout8result

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.