Unique Number Of Occurrences - Leetcode Solution

Problem Statement:

Given an array of integers arr, write a function that returns true if and only if the number of occurrences of each value in the array is unique.

Input:

• An array of integers, arr.

Output:

• Return true if and only if the number of occurrences of each value in the array is unique, else return false.

Example: Input: arr = [1, 2, 2, 1, 1, 3] Output: true Explanation:

• The occurrences of 1 is 3, which is unique.
• The occurrences of 2 is 2, which is unique.
• The occurrences of 3 is 1, which is unique.

Solution:

We can solve the problem by using some data structures such as hash tables and sets.

• We initialize an empty hash table (dictionary) called count.
• We iterate over each element in the input array arr.
  • For each element, we increment its count in the hash table. If the element is not present, we add it to the hash table with count 1.
• We initialize an empty set called counts_set.
• We iterate over the values in count hash table.
  • For each count, we add it to the counts_set. If the count is already present in counts_set, we return false since it means there are two or more values with the same count.
• If we have iterated over all the values in count hash table and have not returned false, we can safely return true since we have found unique counts for all values.

Pseudo-code:

def uniqueOccurrences(arr: List[int]) -> bool: count = {} counts_set = set()

for val in arr:
    if val not in count:
        count[val] = 1
    else:
        count[val] += 1

for val_count in count.values():
    if val_count in counts_set:
        return False
    else:
        counts_set.add(val_count)

return True

Time Complexity:

The time complexity of the above solution is O(n), where n is the length of the input array arr. This is because we iterate over the input array only once and also iterate over the values in count hash table only once.

Space Complexity:

The space complexity of the above solution is O(n), where n is the length of the input array arr. This is because we could potentially store all values of the input array arr in the count hash table.

1