Unique Number of Occurences (via Leetcode)¶

Date published: 2020-03-25

Category: Python

Subcategory: Beginner Algorithms

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

In [ ]:

# assert unique_occurences(arr=[1, 2, 2, 1, 1, 3]) == 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.

In [ ]:

# assert unique_occurences(arr=[1, 2]) == 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).

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

# 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

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

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.