We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Unique Number of Occurrences

Number: 1319

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, Bloomberg, Microsoft, Apple, Adobe, Uber

Problem Description

Given an array of integers, determine if the number of occurrences of each value in the array is unique. If every distinct number appears a unique number of times (i.e., no two distinct numbers have the same count), return true; otherwise, return false.

Key Insights

  • Count the frequency of each integer in the array.
  • Use a hash table (or equivalent data structure) to store frequencies.
  • Check if the set of frequency values has the same length as the frequency list, which ensures uniqueness.
  • Edge cases include arrays with only one element or all elements the same.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the input array, since we traverse the array to build the frequency count. Space Complexity: O(n) in the worst case, when all elements are distinct, to store the frequency counts.

Solution

We first traverse the array and count the frequency of each element using a hash table (or dictionary in Python). Once we have the frequency counts, convert the counts to a set. If the length of the set is equal to the number of unique keys in the frequency dictionary, then each occurrence count is unique. If not, some numbers share the same frequency. This method efficiently checks the uniqueness property with a couple of passes over the data.

Code Solutions

# Count the frequency of each element using a dictionary.
# Then check if the set of frequencies has the same length as the dictionary.
def uniqueOccurrences(arr):
    frequency = {}
    # Count frequency for each element in the input array.
    for num in arr:
        frequency[num] = frequency.get(num, 0) + 1
    
    # Extract all frequency values into a list.
    occurrences = list(frequency.values())
    
    # Use a set to remove duplicates. If lengths are equal, occurrences are unique.
    return len(occurrences) == len(set(occurrences))

# Example usage:
print(uniqueOccurrences([1,2,2,1,1,3]))  # Output: True
← Back to All Questions