Python Beginner Algorithms Tutorial

Unique Number of Occurences (via Leetcode)

Problem Setup

This problem ws found on Leetcode.

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.

Test Cases

In this first test case, there's 3 occurences of 1, 2 occurences of 2, and 1 occurence of 3. Note how 3, 2, and 1 are all different from one another. Therefore, this test case should return True.

In [ ]:
# assert unique_occurences(arr=[1, 2, 2, 1, 1, 3]) == True

In this test case, there's 1 occurence of 1 and 1 occurence of 2. These count of occurences of each unique value are 1; therfore this test case should return False.

In [ ]:
# assert unique_occurences(arr=[1, 2]) == False

Pseudocode

n is the length of items in arr.

The pseudocode below stores a dictionary with a worst case scenario having n keys. Therefore, this dictionary is an O(n) space complexity.

The set created below can also have up to n elements and is therefore O(n) space complexity too.

Therefore, total space complexity is O(2n) but the 2 is negligible relative to the size of n so the total space complexity is just O(n).

I also perform two iterations - one over all elements in arr and another over each element in the dictionary. Therefore, exact time complexity is O(2n). Once again, the 2 is negligible relative to the size of n so the total time complexity is just O(n).

In [ ]:
# create empty dictionary to keep track of count of unique occurences of each element in arr

# iterate over each element in arr
    # if element is not a key in dictionary:
        # access value element in dict and assign value of 1
    # if element is a key in dictionary:
        # access value in dict and increment by 1

# need to see if the count of occurences of any of the elements are the same...
# as we do iteration, we want to return false if we find values among two key-value pairs are the same...

# create an empty set

# iterate over each key-value pair in dict:
    # if value exists in set:
        # return False
    # else:
        # access value and add it to the set
        
# we've reached iteration and have not returned False, so all count of occurences are unique...
# return True

Code

In [6]:
def unique_occurences(arr):
    dict_count_unique_occurrences = {}

    for element in arr:
        if element not in dict_count_unique_occurrences:
            dict_count_unique_occurrences[element] = 1
        else:
            dict_count_unique_occurrences[element] += 1

    set_count_unique_occurences = set()

    for key in dict_count_unique_occurrences:
        the_count = dict_count_unique_occurrences[key]
        if the_count in set_count_unique_occurences:
            return False
        else:
            set_count_unique_occurences.add(the_count)

    return True

Let's evaluate the two test cases to ensure they pass.

In [7]:
assert unique_occurences(arr=[1, 2, 2, 1, 1, 3]) == True
assert unique_occurences(arr=[1, 2]) == False

In alternative to my use of a Python dictionary above, you can use a Python defaultdict.