# Unique Number of Occurences (via Leetcode)

- March 25, 2020
- Key Terms: functions, loops, dictionaries

#### 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`

.

```
# 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`

.

```
# 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).

```
# 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¶

```
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.

```
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.