First Element with Unique Frequency - Solution & Explanation

Problem Overview: You are given an array of integers and need to return the first element whose frequency is unique compared to all other element frequencies. If multiple values appear different numbers of times, only the one whose frequency occurs exactly once should be returned, while also respecting the element's first appearance order in the array.

Approach 1: Brute Force Frequency Comparison (O(n²) time, O(n) space)

Start by computing the frequency of every element using a hash map. Then iterate through the array again and, for each element, check whether any other element has the same frequency. This requires scanning the frequency map for every candidate. If no other element shares that frequency, you found the answer. The approach is straightforward but inefficient because each frequency check can scan up to n entries, leading to quadratic behavior for large inputs.

Approach 2: Hash Table with Frequency-of-Frequency Counting (O(n) time, O(n) space)

The optimal solution uses two hash tables. First, build a frequency map where each number maps to its occurrence count. Next, build a second map that counts how many elements have each frequency. This converts the "is this frequency unique?" check into a constant-time lookup. Finally, iterate through the original array order and return the first element whose frequency appears exactly once in the frequency-count map. This approach relies heavily on constant-time hash lookups and avoids repeated scans.

This pattern appears frequently in problems involving frequency analysis and counting structures. Using a hash table makes counting efficient, while the second map handles uniqueness checks in constant time. The input traversal preserves the "first element" requirement, which is common in array problems where order matters. The counting strategy is also a classic example of counting techniques used in many interview problems.

Recommended for interviews: Interviewers expect the hash table counting solution. The brute force approach demonstrates you understand the definition of frequency uniqueness, but the optimized two-map strategy shows you know how to reduce repeated work and achieve O(n) time. Always mention that the array is scanned twice—once for building counts and once for preserving order—while hash lookups keep each operation constant time.