3843. First Element with Unique Frequency

MediumArrayHash TableCounting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

Your task is to find the first element (scanning from left to right) whose frequency is unique. A frequency is considered unique when no other integer in the array appears that same number of times.

In other words:

First, determine how many times each integer appears in nums.
Then, for each element from left to right, check whether its number of occurrences is shared with any other integer.
The first element whose occurrence count is not shared by any other integer is the answer.

If no element satisfies this condition, return -1.

Example walkthrough:

Suppose nums = [1, 2, 2, 3, 3, 3]. The counts are:

1 appears 1 time
2 appears 2 times
3 appears 3 times

Here, every count (1, 2, 3) is unique, so scanning from left to right, the first element is 1, and its frequency 1 is unique. The answer is 1.

Now suppose nums = [1, 1, 2, 2, 3]. The counts are:

1 appears 2 times
2 appears 2 times
3 appears 1 time

Both 1 and 2 share a frequency of 2, so they are not unique. The element 3 appears 1 time, and no other integer appears exactly 1 time, so its frequency is unique. The answer is 3.

If a case such as nums = [1, 1, 2, 2] is given, both integers appear 2 times, so no frequency is unique and the result is -1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Two-pass hash table approach counts elements and then counts frequencies of counts.

Open in Flowchart

Intuition

The problem asks us to find an element whose frequency (number of occurrences) is unique in the array. To decide whether an element's frequency is unique, we need two pieces of information:

How many times each element appears.
How many elements share each particular frequency.

The first piece tells us the frequency of every element. The second piece lets us check, for any given frequency, whether it is shared by more than one element.

A natural way to capture the first piece is to count the occurrences of each element. For example, if element x appears k times, we record cnt[x] = k.

Once we know every element's count, we can flip the question around: instead of asking "how many times does x appear?", we ask "how many distinct integers appear exactly k times?". By counting the frequencies of the counts themselves, we build a second table freq, where freq[k] tells us how many different integers occur exactly k times.

With these two tables ready, the condition for an element x to have a unique frequency becomes very simple: freq[cnt[x]] must equal 1. This means that the count of x is shared by no other integer.

Finally, because the answer must be the first such element scanning from left to right, we traverse the original array nums in order and return the first element that satisfies freq[cnt[x]] == 1. If we reach the end without finding one, we return -1.

Solution Approach

Solution 1: Hash Table

We use a hash table cnt to count the occurrences of each element, and then use another hash table freq to count the frequency of each occurrence count. Finally, we traverse the array nums again. For each element x, if the value of freq[cnt[x]] is 1, it means the occurrence frequency of x is unique, and we return x. If no such element is found after traversing, return -1.

Step-by-step breakdown:

Build the element count table cnt. We iterate through nums and count how many times each integer appears. Using Python's Counter, this is done in a single line: cnt = Counter(nums). After this step, cnt[x] gives the number of occurrences of element x.
Build the frequency-of-counts table freq. We take the values of cnt (i.e., all the occurrence counts) and count how many integers share each count. With freq = Counter(cnt.values()), the value freq[k] tells us how many distinct integers appear exactly k times. This is the key structure that lets us check uniqueness in O(1) time.
Scan from left to right to find the answer. We traverse nums in its original order. For each element x, we look up freq[cnt[x]]. If this value equals 1, then x's occurrence count is shared by no other integer, so its frequency is unique, and we immediately return x. Returning during the first match guarantees we get the first qualifying element.
Handle the no-answer case. If the loop completes without returning, no element has a unique frequency, so we return -1.

Why this works: By precomputing cnt and freq, the uniqueness check for any element reduces to a constant-time lookup freq[cnt[x]] == 1. The left-to-right scan over nums ensures the first valid element is returned.

Complexity Analysis:

Time complexity: O(n), where n is the length of nums. Building cnt takes O(n), building freq takes at most O(n), and the final scan takes O(n).
Space complexity: O(n), used by the two hash tables cnt and freq in the worst case where all elements are distinct.

Example Walkthrough

Let's trace through the solution approach using a small example: nums = [5, 5, 4, 4, 4, 6].

Step 1: Build the element count table cnt.

We scan through nums and tally each integer's occurrences:

5 appears 2 times
4 appears 3 times
6 appears 1 time

So the table becomes:

cnt = {5: 2, 4: 3, 6: 1}

Step 2: Build the frequency-of-counts table freq.

Now we take the values of cnt, namely [2, 3, 1], and count how many integers share each count:

count 2 is held by 1 integer (just 5)
count 3 is held by 1 integer (just 4)
count 1 is held by 1 integer (just 6)

So the table becomes:

freq = {2: 1, 3: 1, 1: 1}

Step 3: Scan from left to right to find the answer.

We walk through nums in its original order and check freq[cnt[x]] == 1 for each element:

Position	Element `x`	`cnt[x]`	`freq[cnt[x]]`	Unique?
0	`5`	`2`	`1`	✅ Yes

At the very first element 5, we find freq[cnt[5]] = freq[2] = 1, meaning no other integer appears exactly 2 times. Its frequency is unique, so we immediately return 5.

Result: 5

To contrast, consider a case where the first element is not unique, nums = [5, 5, 4, 4, 6]:

cnt = {5: 2, 4: 2, 6: 1}
freq = {2: 2, 1: 1}

Scanning left to right:

Position	Element `x`	`cnt[x]`	`freq[cnt[x]]`	Unique?
0	`5`	`2`	`2`	❌ No
1	`5`	`2`	`2`	❌ No
2	`4`	`2`	`2`	❌ No
3	`4`	`2`	`2`	❌ No
4	`6`	`1`	`1`	✅ Yes

Here 5 and 4 both appear 2 times, so their frequency 2 is shared (freq[2] = 2). Only 6, appearing 1 time, has a frequency that no other integer shares. The answer is 6.

This demonstrates how the precomputed cnt and freq tables let us verify uniqueness in constant time per element, while the left-to-right scan guarantees we return the first qualifying element.

Solution Implementation

1from typing import List
2from collections import Counter
3
4
5class Solution:
6    def firstUniqueFreq(self, nums: List[int]) -> int:
7        # Count how many times each value appears in nums
8        value_counts = Counter(nums)
9
10        # Count how many values share the same frequency
11        # Key: a frequency, Value: number of distinct values having that frequency
12        freq_of_counts = Counter(value_counts.values())
13
14        # Iterate through nums in original order to keep the "first" requirement
15        for num in nums:
16            # If the frequency of the current number is unique
17            # (i.e., no other value shares the same frequency), return it
18            if freq_of_counts[value_counts[num]] == 1:
19                return num
20
21        # No value has a unique frequency
22        return -1
23

1class Solution {
2    public int firstUniqueFreq(int[] nums) {
3        // Step 1: Count the occurrences (frequency) of each number in the array.
4        Map<Integer, Integer> countMap = new HashMap<>();
5        for (int num : nums) {
6            // Merge adds 1 to the existing value, or initializes it to 1 if absent.
7            countMap.merge(num, 1, Integer::sum);
8        }
9
10        // Step 2: Count how many numbers share the same frequency value.
11        // Key: a frequency value, Value: how many numbers have that frequency.
12        Map<Integer, Integer> freqMap = new HashMap<>();
13        for (int count : countMap.values()) {
14            freqMap.merge(count, 1, Integer::sum);
15        }
16
17        // Step 3: Traverse the array in original order to preserve "first" semantics.
18        // Return the first number whose frequency is unique
19        // (i.e., no other number shares that same frequency).
20        for (int num : nums) {
21            if (freqMap.get(countMap.get(num)) == 1) {
22                return num;
23            }
24        }
25
26        // No number with a unique frequency was found.
27        return -1;
28    }
29}
30

1class Solution {
2public:
3    int firstUniqueFreq(vector<int>& nums) {
4        // Step 1: Count the occurrences of each number.
5        unordered_map<int, int> valueCount;
6        for (int value : nums) {
7            ++valueCount[value];
8        }
9
10        // Step 2: Count how many numbers share each frequency.
11        // freqCount[f] = how many distinct numbers appear exactly f times.
12        unordered_map<int, int> freqCount;
13        for (const auto& [value, count] : valueCount) {
14            ++freqCount[count];
15        }
16
17        // Step 3: Traverse the array in order and return the first number
18        // whose frequency is unique (no other number shares that frequency).
19        for (int value : nums) {
20            if (freqCount[valueCount[value]] == 1) {
21                return value;
22            }
23        }
24
25        // No number with a unique frequency was found.
26        return -1;
27    }
28};
29

1/**
2 * Finds the first number in the array whose occurrence count is itself unique.
3 *
4 * A number qualifies when no other distinct number shares the same frequency.
5 * The result is the first such number based on its order of appearance in `nums`.
6 *
7 * @param nums - The input array of numbers.
8 * @returns The first number with a unique frequency, or -1 if none exists.
9 */
10function firstUniqueFreq(nums: number[]): number {
11    // Step 1: Count how many times each number appears.
12    const countMap = new Map<number, number>();
13    for (const num of nums) {
14        countMap.set(num, (countMap.get(num) ?? 0) + 1);
15    }
16
17    // Step 2: Count how many numbers share each frequency value.
18    const freqMap = new Map<number, number>();
19    for (const count of countMap.values()) {
20        freqMap.set(count, (freqMap.get(count) ?? 0) + 1);
21    }
22
23    // Step 3: Scan in original order and return the first number whose
24    // frequency is not shared by any other number.
25    for (const num of nums) {
26        const count = countMap.get(num)!;
27        if (freqMap.get(count) === 1) {
28            return num;
29        }
30    }
31
32    // No number with a unique frequency was found.
33    return -1;
34}
35

Time and Space Complexity

Time complexity: O(n), where n is the length of the array nums. Building the cnt counter from nums takes O(n) time, building the freq counter from cnt.values() takes at most O(n) time, and the final loop iterates over nums performing constant-time lookups, which is also O(n). Therefore, the overall time complexity is O(n).
Space complexity: O(n), where n is the length of the array nums. The cnt counter stores at most n distinct keys, and the freq counter stores at most n distinct frequency values. Hence, the space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing "unique frequency" with "frequency of 1"

A very common misreading of this problem is to assume that a "unique frequency" means the element must appear exactly once. With this misunderstanding, people write code that simply looks for the first element whose count is 1:

# WRONG: This finds the first element that appears exactly once,
# NOT the first element whose frequency is unique.
class Solution:
    def firstUniqueFreq(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        for num in nums:
            if cnt[num] == 1:   # <-- wrong condition
                return num
        return -1

Why it's wrong: Consider nums = [1, 1, 2, 2, 2]. Here 1 appears 2 times and 2 appears 3 times. Both frequencies (2 and 3) are unique, so the correct answer is 1. But the buggy code looks for an element appearing exactly once, finds none, and incorrectly returns -1.

Solution: Compare against the frequency-of-counts table, not the raw count. The condition must be freq_of_counts[value_counts[num]] == 1, which checks that no other integer shares the same occurrence count—regardless of what that count actually is.

Pitfall 2: Comparing `value_counts[num] == 1` instead of `freq_of_counts[...] == 1`

A subtler version of the same mistake is mixing up the two hash tables. It's easy to accidentally write:

if value_counts[num] == 1:        # checks the element's count

when you actually mean:

if freq_of_counts[value_counts[num]] == 1:   # checks if that count is shared

Why it's wrong: value_counts[num] is how many times num appears, while freq_of_counts[value_counts[num]] is how many distinct integers share that appearance count. Uniqueness of a frequency is determined by the latter. Always double-check that the outermost lookup is into freq_of_counts.

Pitfall 3: Losing the left-to-right order

If you iterate over value_counts (a dictionary) or over freq_of_counts instead of over nums, you may return a valid element, but not the first one in the original array order.

# WRONG: iteration order of the counter does not reflect nums' order
for num in value_counts:
    if freq_of_counts[value_counts[num]] == 1:
        return num

Why it's wrong: Although Python 3.7+ preserves insertion order in dictionaries (so Counter reflects first-appearance order), relying on this is fragile and the intent is unclear. More importantly, in other languages a hash map has no guaranteed order, so this approach breaks entirely.

Solution: Always perform the final scan over the original nums array. This guarantees the first qualifying element is returned, matching the problem's requirement explicitly and portably.

Pitfall 4: Forgetting the `-1` fallback

When every frequency is shared (e.g., nums = [1, 1, 2, 2]), no element qualifies. Omitting the final return -1 causes the function to implicitly return None, which fails the test cases.

Solution: Always include return -1 after the loop to explicitly handle the "no unique frequency" case.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering