Print Only Unique Values in an Array - Java

Category: Medium | Concepts used: Frequency counting, filtering

---

Problem Statement

Given an array, print only the values that appear exactly once (not the same as “distinct values” — this excludes anything that repeats at all).

Input : [1, 2, 2, 3, 4, 4, 5]      Output: [1, 3, 5]

Note: This is different from “distinct values” (Q19/Q28 concept) — a value appearing 3 times is not unique here, but it IS one of the “distinct” values.

Examples (with edge scenarios)

#	Input	Output	Why
1	[1, 2, 2, 3, 4, 4, 5]	[1, 3, 5]	Only values appearing exactly once
2	[] (empty)	[]	Nothing to check
3	[1, 1, 1]	[]	Repeats 3 times — not unique at all
4	[7] (single element)	[7]	Appears once — trivially unique
5	[1, 2, 3] (all distinct)	[1, 2, 3]	Every value appears exactly once

Common Fresher Mistake

Mistake	What happens	Fix
Confusing “unique” (appears exactly once) with “distinct” (appears at all, ignoring count)	Wrong output — e.g., including a value that appears 3 times	Always clarify which definition the interviewer means before coding
Trying to filter and print in a single pass without first knowing the full frequency count	You’d have to look ahead in the array, which a single forward pass can’t do cleanly	Build a full frequency map FIRST, then do a second pass to filter based on it

---

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 Single-copy Book Collector

Imagine you are sorting a box of donated books for a library. You want to identify books that are “unique” (meaning the box contains exactly one copy of that title):

• If you pull a book out of the box, you can’t decide if it is unique immediately, because there might be another copy of the same book sitting at the bottom of the box.
• So, you first sort all books into stacks by title and count them (Pass 1 - building the frequency map).
• Once all books are stacked, you go through the stacks in the order you found them (Pass 2 - filtering).
• If a stack has a height of exactly 1 book, you put it on the display shelf. If a stack has 2 or more books, you ignore them all!

---

Solution 1 — Frequency Map, Then Filter (Two Passes)

Intuition

To know if a number is “unique” (appears exactly once), you need to know its total count across the whole array — which you can’t know while still partway through your first look at the array. So: first pass, build a complete frequency map of every value; second pass, walk through again and only keep values whose recorded count is exactly 1.

import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;

public class UniqueValues {
    public static List<Integer> findUniqueValues(int[] arr) {
        HashMap<Integer, Integer> freq = new HashMap<>();

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

// Pass 2: keep only values with count == 1, preserving original order
        List<Integer> result = new ArrayList<>();
        for (int num : arr) {
            if (freq.get(num) == 1) {
                result.add(num);
            }
        }
        return result;
    }

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

Output:

[1, 3, 5]
[]
[]

Dry Run (arr = [1, 2, 2, 3])

Pass 1 - build freq map:
1 -> freq={1:1}
2 -> freq={1:1, 2:1}
2 -> freq={1:1, 2:2}
3 -> freq={1:1, 2:2, 3:1}

Pass 2 - filter:
num=1: freq.get(1)=1 -> keep -> result=[1]
num=2: freq.get(2)=2 -> skip
num=2: freq.get(2)=2 -> skip
num=3: freq.get(3)=1 -> keep -> result=[1,3]

Final: [1, 3]

Interviewer’s take

This is exactly the expected approach — a very common and reusable pattern (“count first, then filter based on counts”) that appears across many similar problems. The two-pass structure is intentional and correct here, not a sign of inefficiency — trying to force this into a single pass would actually make the logic more convoluted, not less.

Follow-up questions you might get:

• “Why does the second pass iterate over the original array instead of the map’s keys?” → To preserve the original order of appearance in the output. Iterating over the map’s keys wouldn’t guarantee that (with a plain HashMap).
• “What’s the time and space complexity?” → O(n) time (two linear passes), O(n) space for the frequency map.
• “How is this different from finding distinct values?” → ‘Distinct’ would include every value that appears at all (even repeated ones), just listed once each; ‘unique’ here specifically excludes anything that repeats.

---

📊 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: Filter Unique Items"]
    Pass2 --> Loop2{"j < arr.length?"}
    Loop2 -->|Yes| CheckFreq{"freqMap[arr[j]] == 1?"}
    CheckFreq -->|Yes| Keep["Add arr[j] to result"]
    CheckFreq -->|No| Skip["Skip arr[j]"]
    Keep --> Next2["j++"]
    Skip --> Next2
    Next2 --> Loop2
    Loop2 -->|No| End["Return result list"]

---

Final Verdict — Which Solution Should You Give?

• Solution 1 (two-pass with HashMap) is the standard, expected, and correct approach. There isn’t really a “less optimal starting point” here worth mentioning first — this two-pass pattern is the natural, correct solution from the start.
• The biggest signal an interviewer looks for is confirming you understand the “unique” vs “distinct” distinction before writing any code.

---

Quick Recap

Approach	Time	Space	Interview Signal
Two-pass frequency map + filter	O(n)	O(n)	Standard, correct pattern