Unique Number of Occurrences

Difficulty: Easy | Acceptance: 78.70% | Paid: No Topics: Array, Hash Table

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

Table of Contents

• Examples
• Constraints
• Hash Map and Set
• Sorting
• Fixed Array Counting

Examples

Example 1:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 occurrences and 3 has 1 occurrence. 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

Hash Map and Set

Intuition We can use a hash map to count the frequency of each number. Then, we iterate through the frequency values and check for duplicates using a hash set.

Steps

• Initialize a hash map to store the count of each number in the array.
• Iterate through the array and populate the hash map.
• Initialize a hash set to track seen frequencies.
• Iterate through the values (frequencies) of the hash map.
• If a frequency is already in the set, return false (duplicate found).
• Otherwise, add the frequency to the set.
• If the loop finishes without returning false, return true.

from collections import Counter

class Solution:
    def uniqueOccurrences(self, arr: list[int]) -> bool:
        counts = Counter(arr)
        seen = set()
        for count in counts.values():
            if count in seen:
                return False
            seen.add(count)
        return True

Complexity

• Time: O(n)
• Space: O(n)
• Notes: We use O(n) space for the map and set. This is the most general solution.

Sorting

Intuition If we sort the array, identical numbers will be adjacent. We can then iterate through the sorted array to count the frequency of each number and check for duplicates in those frequencies.

Steps

• Sort the input array in ascending order.
• Initialize a set to store frequencies.
• Iterate through the sorted array using a pointer.
• For each unique number, count how many times it appears consecutively.
• Check if this count exists in the set. If yes, return false.
• Add the count to the set and move the pointer to the next new number.
• Return true if the loop completes.

class Solution:
    def uniqueOccurrences(self, arr: list[int]) -> bool:
        arr.sort()
        seen = set()
        i = 0
        n = len(arr)
        while i < n:
            current = arr[i]
            count = 0
            while i < n and arr[i] == current:
                count += 1
                i += 1
            if count in seen:
                return False
            seen.add(count)
        return True

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Sorting takes O(n log n) time. We still need O(n) space in the worst case for the set of frequencies.

Fixed Array Counting

Intuition The problem constraints state that -1000 <= arr[i] <= 1000. This range is small (2001 possible values). We can use a fixed-size array instead of a hash map to count frequencies, which is often faster.

Steps

• Create an array counts of size 2001 initialized to 0.
• Iterate through the input array. For each number num, increment counts[num + 1000] (shifting the index to be non-negative).
• Iterate through the counts array to collect non-zero frequencies into a set.
• If the size of the set equals the number of unique values found, return true. Otherwise, return false.

class Solution:
    def uniqueOccurrences(self, arr: list[int]) -> bool:
        offset = 1000
        counts = [0] * 2001
        for num in arr:
            counts[num + offset] += 1
        
        seen = set()
        for count in counts:
            if count > 0:
                if count in seen:
                    return False
                seen.add(count)
        return True

Complexity

• Time: O(n)
• Space: O(1)
• Notes: The space complexity is O(1) because the auxiliary array size is fixed (2001) regardless of the input size n.