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 :
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:

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