Skip to main content
Talentd

Unique Number of Occurrences - Solution & Explanation

EasyArrayHash Table13 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.

 

Example 1:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Example 2:

Input: arr = [1,2]
Output: false

Example 3:

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true

 

Constraints:

  • 1 <= arr.length <= 1000
  • -1000 <= arr[i] <= 1000

Approach Overview

Problem Overview: You receive an integer array and need to verify whether the frequency of every value is unique. If two different numbers appear the same number of times, the result is false. Otherwise, return true.

Approach 1: Hash Map and Set (O(n) time, O(n) space)

The direct solution uses a frequency counter. Iterate through the array and store counts in a hash map where the key is the number and the value is its occurrence count. After building the map, iterate over the frequency values and insert them into a set. A set automatically removes duplicates, so if any frequency repeats, the set size will be smaller than the number of unique elements.

This works because hash lookups and insertions run in constant average time. The key insight is separating the problem into two steps: counting occurrences and verifying uniqueness of those counts. The array is scanned once to build frequencies and once more to validate uniqueness, giving O(n) time complexity and O(n) space for the hash structures. This method is commonly implemented with a hash table from the Hash Table family while iterating over the Array.

Approach 2: Sorting and Comparison (O(n log n) time, O(n) space)

Another option avoids a set by sorting the frequency values. First compute counts using a hash map. Extract the frequencies into a list and sort them. After sorting, duplicate frequencies become adjacent, so a single linear scan can detect whether two consecutive counts are equal.

The main cost comes from sorting the frequency list, which takes O(k log k) where k is the number of distinct elements. In the worst case k = n, giving O(n log n) time complexity. Space usage remains O(n) due to the frequency map and the list used for sorting. This approach is sometimes preferred when you already rely on sorting for additional processing or want a simple comparison-based check.

Recommended for interviews: The hash map + set approach is the expected solution. It demonstrates correct use of frequency counting and constant-time membership checks. Interviewers often accept the sorting method, but the linear-time hash solution shows stronger understanding of hash-based data structures and optimal complexity.

Approach 1: Hash Map and Set

In this approach, we will first traverse the array to count the occurrences of each element using a hash map. Then, we will use a set to check if these occurrences are unique. If the size of the set matches the size of the occurrence counts, it implies all occurrences are unique.

In the C implementation, we use an array count to store the frequency of each element adjusted by 1000 to handle negative indices. The hash array is used to ensure all frequencies are unique.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since we're using fixed-size arrays.

Try this approach in the editor →

Approach 2: Sorting and Comparison

This alternative approach starts by counting occurrences just like the first one. After that, it stores these counts in a list, sorts the list, and then checks for any consecutive equal elements, which would indicate duplicate occurrences.

In the C implementation using sorting, we use qsort to sort the frequency array and then check if any consecutive elements are equal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), since we work within fixed-sized arrays.

Try this approach in the editor →

Approach 3: Hash Table

We use a hash table cnt to count the frequency of each number in the array arr, and then use another hash table vis to count the types of frequencies. Finally, we check whether the sizes of cnt and vis are equal.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array arr.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Hash Map and Set

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since we're using fixed-size arrays.

Sorting and Comparison

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), since we work within fixed-sized arrays.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map and SetO(n)O(n)General case. Fastest solution using frequency counting and set uniqueness check.
Sorting and ComparisonO(n log n)O(n)Useful when frequency values are already being sorted or when avoiding a set.

Video Solution

LeetCode 1207. Unique Number of Occurrences (Algorithm Explained) • Nick White • 21,116 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Unique Number of Occurrences easy or hard?
LeetCode classifies this problem as Easy. The challenge mainly tests understanding of frequency counting and set-based uniqueness checks. Developers comfortable with hash maps and basic array traversal typically solve it quickly.
Unique Number of Occurrences Python/Java solution
In Python, use collections.Counter or a dictionary to count frequencies, then compare the length of the frequency list with the length of a set built from it. In Java, use HashMap<Integer, Integer> for counting and HashSet<Integer> for uniqueness checks. Both implementations run in O(n) time.
How to solve Unique Number of Occurrences in O(n)?
Use a hash map to count how many times each number appears. Then iterate through the frequency values and insert them into a set. If a frequency already exists in the set, two numbers share the same occurrence count and the answer is false. Otherwise, all counts are unique, producing a true result in O(n) time.
What is the best approach for Unique Number of Occurrences?
The hash map and set approach is the most efficient and commonly expected solution. First count each number's frequency using a hash map, then insert the counts into a set to ensure all frequencies are unique. If the number of frequencies equals the set size, all counts are unique. This runs in O(n) time and O(n) space.
Is Unique Number of Occurrences asked at Google/Amazon/Meta?
Frequency counting and hash table validation problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the pattern of counting elements and verifying constraints using hash structures is a common interview topic.
What data structure is used in Unique Number of Occurrences?
The primary data structures are a hash map and a set. The hash map stores element frequencies, and the set checks whether those frequencies repeat. Both provide constant-time average insert and lookup operations, enabling an O(n) solution.
What is the time complexity of Unique Number of Occurrences?
The optimal solution runs in O(n) time where n is the array length. Building the frequency map requires one pass through the array, and inserting counts into a set is another linear pass. Hash operations are constant time on average, so the overall complexity remains O(n) with O(n) additional space.

Ready to solve this problem?

Practice Unique Number of Occurrences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays