Unique Number of Occurrences
Problem
Given an array of integers arr, return true if the number of occurrences of each value in the array is unique, and false otherwise.
- 1 ≤ arr.length ≤ 1000
- −1000 ≤ arr[i] ≤ 1000
Example
arr = [1,2,2,1,1,3]trueCounting the occurrences yields {1:3, 2:2, 3:1}. The frequencies are [3, 2, 1], which are all unique. Therefore, the function returns true.
Approach
Straightforward Solution
A naive approach would count frequencies and then compare each frequency against all others to detect duplicates, resulting in O(n²) time complexity, which is inefficient for larger inputs.
Core Observation
The problem reduces to verifying that the frequency counts of each distinct element are all unique. This means no two elements share the same count.
Path to Optimal
PreviewThe key insight is to use a hash map (or Counter) to count frequencies in O(n) time, then convert the frequency values into a set to detect duplicates efficiently…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse Python's Counter to count occurrences, extract the frequency values into a list, and compare the length of this list to the length of the set of frequencies. If equal, all frequencies are unique; otherwise, duplicates exist…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Counting frequencies with Counter takes O(n) time, and creating a set from the frequency values also takes O(n) time. The overall complexity is linear in the size of the input array.
Space
O(n)
The Counter stores frequencies for up to n distinct elements, and the set stores up to n frequency values. Both scale linearly with input size, which is necessary to track counts.
Pattern Spotlight
Hash Maps (Frequency Counting and Uniqueness Check)
When verifying uniqueness of counts or values derived from elements, transform the problem into frequency counting with a hash map, then use a set to detect duplicates efficiently by comparing sizes.
Solution
| 1 | from collections import Counter |
| 2 | |
| 3 | class Solution: |
| 4 | def uniqueOccurrences(self, arr: list[int]) -> bool: |
| 5 | count = Counter(arr) |
| 6 | frequencies = list(count.values()) |
| 7 | |
| 8 | return len(frequencies) == len(set(frequencies)) |
Step-by-Step Solution
Count Element Frequencies Using Counter
| 5 | count = Counter(arr) |
Objective
To efficiently count how many times each distinct integer appears in the input array.
Key Insight
Using a hash map-like data structure such as Counter allows counting frequencies in a single pass with O(n) time. This transforms the problem from dealing with raw elements to dealing with their occurrence counts, which is the core data needed to check uniqueness.
Interview Quick-Check
Core Logic
Counter builds a frequency map in O(n) time by iterating once over the input array.
Common Pitfalls & Bugs
Manually counting frequencies with nested loops leads to O(n²) time, which is inefficient.
Extract Frequencies and Compare Uniqueness via Set
To determine if all frequency counts are unique by comparing the list of frequencies to a set of those frequencies.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
return len(frequencies) == len(set(frequencies))Return whether all frequency counts are unique by comparing the length of the frequency list to the length of the set of frequencies.
Sets automatically remove duplicates, so if the lengths differ, it means some frequencies are repeated; if equal, all frequencies are unique. This comparison is a concise and efficient way to verify uniqueness.
count = Counter(arr)Count the occurrences of each integer in the input array using Counter.
Counter efficiently builds a frequency map in O(n) time by hashing each element and incrementing its count, enabling fast frequency retrieval for all distinct elements.
Full line-by-line criticality + rationale for all 3 lines available on Pro.
Test Your Understanding
Why does comparing the length of the frequency list to the length of the set of frequencies determine uniqueness?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Unique Number of Occurrences from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Unique Number of Occurrences drill