[LeetCode] 1207. Unique Number of Occurrences

1. Question

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

2. Thoughts

As we would need to access the occurance of each element,
we can save the element and occurance in a dictionary(which uses hash map)
then, use set to add and find if element exists(which also uses hash map)

3. Tips learned

collections.Counter is a subclass of the dict class in Python's collections module. It's designed for counting hashable objects, essentially providing a way to tally occurrences of items in an iterable or initialization from another mapping (like a dictionary) or keyword arguments.

Here's a breakdown of some key features and methods that Counter provides:

1. Creating a Counter: A Counter can be instantiated from an iterable (like a list or a string) or a mapping (like a dictionary). For example:

   from collections import Counter
   
   # From an iterable
   c = Counter(['a', 'b', 'c', 'a', 'b', 'b'])
   
   # From a mapping
   d = Counter({'a': 2, 'b': 3, 'c': 1})
   
   # From keyword arguments
   e = Counter(a=2, b=3, c=1)

2. Accessing Counts: Once instantiated, you can access the count of each element using dictionary syntax:

   print(c['a'])  # Output: 2
   print(c['b'])  # Output: 3

3. Updating Counts: You can update the count of elements using the update() method:

   c.update(['a', 'b', 'a', 'c'])

4. Automatic Handling of Missing Values: If you request the count of an element that hasn't been added to the Counter, it will return 0 rather than raise a KeyError:

   print(c['d'])  # Output: 0

5. Methods for Arithmetic: Counter objects support addition, subtraction, intersection, and union:

   c1 = Counter(a=3, b=1)
   c2 = Counter(a=1, b=2)
   print(c1 + c2)  # combine counts
   print(c1 - c2)  # subtract (keeping only positive counts)

6. most_common([n]) Method: This method returns a list of the n most common elements and their counts from the most common to the least. If n is omitted, most_common() returns all elements in the counter. Elements with equal counts are ordered arbitrarily:

   print(c.most_common(2))

7. elements() Method: Returns an iterator over elements repeating each as many times as its count. Elements are returned in the order first encountered:

   list(c.elements())

8. Counter as a Subclass of Dictionary: Since Counter is a dictionary subclass, it has all the methods of dict (like keys(), values(), items(), etc.) but it includes additional utility methods suitable for tallying.

Counter is very useful for problems involving counting and tallying objects, and it simplifies code that would otherwise require manually incrementing dictionary values or using defaultdict(int).

4. My solution

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        elements = {}
        for element in arr:
            if element in elements:
                elements[element] += 1
            else:
                elements[element] = 1

        occurance = set()
        for element in elements:
            if elements[element] in occurance:
                return False
            occurance.add(elements[element])
        return True

67/67 cases passed (48 ms)
Your runtime beats 29.1 % of python3 submissions
Your memory usage beats 86.17 % of python3 submissions (16.3 MB)

5. AI Solution and Improvements

Your solution correctly implements the logic needed to solve the problem: it counts the occurrences of each element and then checks if these counts are unique. The use of a dictionary to count occurrences and a set to check for uniqueness is efficient.

However, we can slightly optimize and make your code more Pythonic by using collections.Counter to count the occurrences and then checking if the number of occurrences has the same length as the set of occurrences, like this:

from collections import Counter

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

This code does the following:

• Counter(arr).values() counts how many times each element appears in arr and returns a dictionary-like object of those counts.
• We then compare the length of the values (which are the occurrence counts) with the length of the set of those values. If the lengths are equal, it means all occurrence counts are unique.

This is a more concise and Pythonic way of solving the problem, using built-in libraries designed for these exact purposes.