Find the First Non-Repeating Element in an Integer Array - Java

Category: Medium | Concepts used: Frequency map, order-preserving lookup (LinkedHashMap)

---

Problem Statement

Given an array, find the first element (by position) that appears exactly once.

Input : [4, 5, 1, 2, 0, 4]      Output: 5   (5 is the first value appearing only once)

Examples (with edge scenarios)

#	Input	Output	Why
1	[4, 5, 1, 2, 0, 4]	5	4 repeats; 5 is the first value with count 1
2	[]	None	Nothing to check
3	[1, 1, 1]	None	No element appears exactly once
4	[7] (single element)	7	Trivially the first (and only) non-repeating element
5	[1, 2, 1, 2] (all repeat)	None	No unique element exists

Common Fresher Mistake

Mistake	What happens	Fix
Using a plain HashMap and expecting the scan order to match array order	HashMap iteration order isn’t guaranteed to match insertion order	Either use a LinkedHashMap, or (better) scan the ORIGINAL array in the second pass, not the map’s keys
Returning “not found” without a clear signal (e.g., returning -1 when -1 could be a valid array value)	Ambiguous result — is -1 a real answer, or “not found”?	Use Integer (nullable) and return null, or use Optional<Integer>, to avoid sentinel-value ambiguity

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: The Ticket Registry Checklist

Imagine you are managing a VIP entrance at a concert hall where guests check in with a registration number (the elements of the array):

• You want to identify the earliest guest who arrived who has a completely unique ticket number (no duplicates checked in at all):
  • Pass 1 (Tallying): As guests walk through the gates, you write down their ticket number on a clipboard sheet and add tick marks for every repeat.
  • Pass 2 (Verification scan): Once everyone is seated, you walk down the arrival queue in the exact order they came in:
    • Guest 1 holding Ticket #4 has a tally of 2 (someone else had the same ticket). Skip.
    • Guest 2 holding Ticket #5 has a tally of exactly 1 (their ticket is unique).
  • You immediately stop scanning and declare Ticket #5 the winner!

---

Solution 1 — Frequency Map + Second Pass Over Original Array (Recommended)

Intuition

Same two-pass pattern used for “first repeating character” — but flipped. First, count every value’s total occurrences. Then, scan the original array again in order, and return the first value whose count is exactly 1. Scanning the original array (not the map’s keys) guarantees we respect the true positional order, regardless of how the map internally stores things.

import java.util.HashMap;

public class FirstNonRepeating {
    public static Integer firstNonRepeating(int[] arr) {
        HashMap<Integer, Integer> freq = new HashMap<>();

// Pass 1: build frequency counts
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

// Pass 2: scan original array in order, return first with count == 1
        for (int num : arr) {
            if (freq.get(num) == 1) {
                return num;
            }
        }
        return null; // no non-repeating element found
    }

public static void main(String[] args) {
        System.out.println(firstNonRepeating(new int[]{4, 5, 1, 2, 0, 4})); // 5
        System.out.println(firstNonRepeating(new int[]{1, 1, 1}));            // null
        System.out.println(firstNonRepeating(new int[]{7}));                   // 7
    }
}

Output:

5
null
7

Dry Run (arr = [4, 5, 1, 2, 0, 4])

Pass 1 - freq map:
freq = {4:2, 5:1, 1:1, 2:1, 0:1}

Pass 2 - scan original array in order:
num=4: freq.get(4)=2, not 1 -> skip
num=5: freq.get(5)=1 -> MATCH! -> return 5

Interviewer’s take

This is exactly the expected solution — correctly using the original array (not the map’s key set) for the second pass is the crucial detail, since it guarantees the true first-occurrence order regardless of HashMap’s internal ordering behavior. Very reusable pattern.

Follow-up questions you might get:

• “Why scan the original array again instead of iterating the map directly?” → A HashMap’s iteration order isn’t guaranteed to reflect insertion order — scanning the original array sidesteps that issue entirely, guaranteeing correctness regardless of map implementation details.
• “How would you signal ‘not found’ cleanly?” → Using a nullable Integer return type (as shown) works well; alternatively, Optional<Integer> is a more explicit, modern approach for signaling absence.
• “What’s the time and space complexity?” → O(n) time (two linear passes), O(n) space for the frequency map.

---

📊 Visual Flowchart

graph TD
    Start["Input: Array arr"] --> Pass1["Pass 1: Count Frequencies"]
    Pass1 --> Loop1{"i < arr.length?"}
    Loop1 -->|Yes| MapInc["freqMap[arr[i]]++"]
    MapInc --> Next1["i++"]
    Next1 --> Loop1
    Loop1 -->|No| Pass2["Pass 2: Scan in original order"]
    Pass2 --> Loop2{"j < arr.length?"}
    Loop2 -->|Yes| CheckFreq{"freqMap[arr[j]] == 1?"}
    CheckFreq -->|Yes| RetVal["Return arr[j]"]
    CheckFreq -->|No| Next2["j++"]
    Next2 --> Loop2
    Loop2 -->|No| RetNull["Return null"]

---

Final Verdict — Which Solution Should You Give?

• Solution 1 is the standard, correct approach for this problem — the two-pass pattern (count, then re-scan original order) is the expected and appropriate technique.
• The subtle but important detail — re-scanning the original array, not the map’s keys — is exactly what separates a correct answer from a subtly buggy one.

---

Quick Recap

Approach	Time	Space	Interview Signal
Frequency map + re-scan original array	O(n)	O(n)	Standard, correct — order-preservation detail matters