#1207

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Unique Number of Occurrences

Determine if each integer in an array occurs a unique number of times using efficient hash-based counting and verification.

array hash table

Problem Statement

Given an array of integers, determine whether the number of occurrences of each element is unique. Return true if all counts are distinct, otherwise return false.

For example, given arr = [1,2,2,1,1,3], the number 1 occurs 3 times, 2 occurs 2 times, and 3 occurs once. Since no two numbers share the same occurrence count, the output is true. If arr = [1,2], the output is false because both numbers occur once, violating uniqueness.

Examples

Example 1

Input: arr = [1,2,2,1,1,3]

Output: true

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 details omitted.

Example 3

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

Output: true

Example details omitted.

Constraints

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

Solution Approach

Count element frequencies with a hash map

Scan the array once and store each element's occurrence in a hash map. Each key represents a number and its value represents the count. This ensures we capture frequency efficiently for subsequent uniqueness checking.

Verify uniqueness of counts using a set

Iterate over the values of the hash map and insert them into a set. If a count already exists in the set, return false immediately. Otherwise, continue until all counts are confirmed unique.

Return the final result

If all occurrence counts were successfully added to the set without duplicates, return true. This completes the array scanning plus hash lookup pattern and guarantees correct verification of unique frequencies.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for a single pass through the array to build the hash map plus O(n) to check uniqueness, yielding O(n) overall. Space complexity is O(n) for storing counts in the hash map and potentially O(n) for the set storing unique frequencies.

What Interviewers Usually Probe

Can you implement this in one pass for counting and a second pass for uniqueness checking?
What happens if the array contains negative numbers or zeros?
How would your solution change if the array size increased to millions of elements?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle negative numbers correctly in the hash map.
Checking counts in-place instead of using a separate set, leading to false positives.
Assuming sorted arrays or consecutive numbers, which is not required.

Follow-up variants

Check if occurrences are unique but allow at most two numbers to share the same count.
Determine unique occurrences without using extra space, modifying the input array.
Return the list of numbers that violate unique occurrence rules instead of just true/false.

FAQ

What does 'Unique Number of Occurrences' mean in this problem?

It means that each integer in the array appears a different number of times, so no two numbers share the same occurrence count.

Can I solve this without a hash map?

You could sort the array and count occurrences manually, but this would increase time complexity and may be less efficient than hash map counting.

How do negative numbers affect the solution?

Negative numbers are treated like any other number and can be stored as keys in the hash map without special handling.

What is the best data structure for checking uniqueness of counts?

A set is ideal because it allows O(1) average time checks for duplicates while iterating over frequency counts.

Why is this problem categorized as 'Array scanning plus hash lookup'?

Because it involves scanning the array to collect frequencies and using a hash map and set to efficiently track and verify uniqueness of these counts.

terminal

Solution

Solution 1: 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.

1

2

3

4

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        cnt = Counter(arr)
        return len(set(cnt.values())) == len(cnt)

Continue Practicing

#1202 smallest string with swaps #1218 longest arithmetic subsequence of given difference #1224 maximum equal frequency