Given a list, find if frequencies of each element of values are in itself unique values.
Input : test_list = [4, 3, 2]
Output : False
Explanation : All have 1 as frequency, hence duplicacy, hence FalseInput : test_list = [4, 3, 3, 2, 2, 2]
Output : True
Explanation : 1, 2, 3 are frequencies of 4, 3, 2 respectively, unique, hence True
Method #1 : Using loop + set()
The combination of above functionalities provide brute force way to solve this problem. In this, we memoize the frequency of elements by incrementing the index of value occurred. Then set() is used to remove duplicates and test if it’s length is same as before the conversion.
Python3
# Python3 code to demonstrate working of # Test for Unique Frequencies# Using loop + set()# initializing listtest_list = [4, 3, 2, 2, 3, 4, 4, 4, 1, 2]# printing original list print("The original list : " + str(test_list))# Test for Unique Frequenciesres = Falsetemp = [0] * 5for ele in test_list: # performing memoization in temp list temp[ele] += 1mem_list = temp[1:]# checking for set converted list length with original listif len(list(set(mem_list))) == len(mem_list): res = True # printing result print("Are element's Frequencies Unique ? : " + str(res)) |
The original list : [4, 3, 2, 2, 3, 4, 4, 4, 1, 2] Are element's Frequencies Unique ? : True
Time complexity: O(n), where n is the length of the input list.
Auxiliary Space: O(1), because the size of the temp list is fixed to 5 and does not depend on the size of the input list. Therefore, the space complexity is constant.
Method #2 : Using setdefault() + values()
The combination of above functions offers yet another way to solve this problem. In this, dictionary is used to memoize and element frequency is recorded as values. At last, similar step of extracting values and dictionary keys count is compared for equality.
Python3
# Python3 code to demonstrate working of # Test for Unique Frequencies# Using setdefault() + values()# initializing listtest_list = [4, 3, 2, 2, 3, 4, 4, 4, 1, 2]# printing original list print("The original list : " + str(test_list))# Test for Unique Frequencies# Using setdefault() + values()temp = {}for ele in test_list: # setting default value to 0 temp.setdefault(ele, 0) temp[ele] += 1# checking for values and keys equalityres = len(set(temp.values())) == len(temp) # printing result print("Are element's Frequencies Unique ? : " + str(res)) |
The original list : [4, 3, 2, 2, 3, 4, 4, 4, 1, 2] Are element's Frequencies Unique ? : True
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n)
Method #3: Using set(),count() and sort() methods
Python3
# Python3 code to demonstrate working of# Test for Unique Frequencies# initializing listtest_list = [4, 3, 2, 2, 3, 4, 4, 4, 1, 2]# printing original listprint("The original list : " + str(test_list))x=list(set(test_list))a=[]for i in x: a.append(test_list.count(i))res=Falseb=list(set(a))b.sort()a.sort()if(b==a): res=True# printing resultprint("Are element's Frequencies Unique ? : " + str(res)) |
The original list : [4, 3, 2, 2, 3, 4, 4, 4, 1, 2] Are element's Frequencies Unique ? : True
Time Complexity: O(nlogn), where n is the number of elements in the list “test_list”.
Auxiliary Space: O(1), constant extra space required
Method #4: Using Counter() function
Python3
# Python3 code to demonstrate working of# Test for Unique Frequencies# Using Counter() functionfrom collections import Counter# initializing listtest_list = [4, 3, 2, 2, 3, 4, 4, 4, 1, 2]# printing original listprint("The original list : " + str(test_list))res = False# Test for Unique Frequenciesfreq = Counter(test_list)valuesFreq = Counter(list(freq.values()))# checking for set converted list length with frequencyif len(valuesFreq) == len(list(freq.values())): res = True# printing resultprint("Are element's Frequencies Unique ? : " + str(res)) |
The original list : [4, 3, 2, 2, 3, 4, 4, 4, 1, 2] Are element's Frequencies Unique ? : True
Time complexity: O(n), where n is the length of the input list test_list.
Auxiliary space: O(n), where n is the length of the input list test_list.
Method 5: using operator.countOf() method
Python3
# Python3 code to demonstrate working of# Test for Unique Frequenciesimport operator as op# initializing listtest_list = [4, 3, 2, 2, 3, 4, 4, 4, 1, 2]# printing original listprint("The original list : " + str(test_list))x = list(set(test_list))a = []for i in x: a.append(op.countOf(test_list, i))res = Falseb = list(set(a))b.sort()a.sort()if(b == a): res = True# printing resultprint("Are element's Frequencies Unique ? : " + str(res)) |
The original list : [4, 3, 2, 2, 3, 4, 4, 4, 1, 2] Are element's Frequencies Unique ? : True
Time Complexity: O(NLogN)
Auxiliary Space : O(1)
Method 6: using dictionary method:
Python3
test_list = [4, 3, 2, 2, 3, 4, 4, 4, 1, 2]print("The original list : ", test_list)counter = {}for ele in test_list: if ele in counter: counter[ele] += 1 else: counter[ele] = 1res = len(counter.values()) == len(counter)print("Are element's Frequencies Unique ? : ", res)#This is code contributed by Jyothi pinjala. |
The original list : [4, 3, 2, 2, 3, 4, 4, 4, 1, 2] Are element's Frequencies Unique ? : True
Time Complexity: O(N)
Auxiliary Space: O(N)
Method #7: Using numpy.unique()
Use the numpy library to find unique elements and their count. The unique() function in numpy returns a sorted array of unique values and their corresponding count.
Python3
test_list = [4, 3, 2, 2, 3, 4, 4, 4, 1, 2]print("The original list : ", test_list)unique_values = set(test_list)counts = [test_list.count(val) for val in unique_values]counts.sort()res = counts == list(range(1, len(counts) + 1))print("Are element's Frequencies Unique ? : ", res) |
The original list : [4, 3, 2, 2, 3, 4, 4, 4, 1, 2] Are element's Frequencies Unique ? : True
Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list
Method 8:Using itertools
Here’s an algorithm for the given code:
- Define the input list test_list
- Use the Counter function from the collections module to count the frequency of each element in test_list. Store the result in a dictionary called freq, where each key represents an element in test_list and the corresponding value represents its frequency.
- Use the itertools.combinations function to generate all possible pairs of values from the dictionary freq.
- For each pair of values (x, y) generated in step 3, check if x is equal to y. If any pair of values is equal, set the result variable res to False and exit the loop.
- If all pairs of values are unequal, set res to True.
- Print the final value of res.
Python3
import itertoolsfrom collections import Countertest_list = [4, 3, 2, 2, 3, 4, 4, 4, 1, 2]freq = Counter(test_list)res = all(x != y for x, y in itertools.combinations(freq.values(), 2))print("Are element's Frequencies Unique ? : ", res)#This code is contributed by Vinay Pinjala. |
Are element's Frequencies Unique ? : True
The time complexity of this code is O(n^2), where n is the length of the input list test_list. This is because the Counter function from the collections module takes O(n) time to count the frequency of each element in test_list. The itertools.combinations function generates n*(n-1)/2 pairs of values, which takes O(n^2) time. The loop that checks if each pair of values is equal takes constant time, so the overall time complexity of the code is O(n^2).
The auxiliary space of this code is O(n), where n is the length of the input list test_list. This is because the Counter function creates a dictionary that stores the frequency of each element in test_list, which takes O(n) space. The itertools.combinations function and the loop that checks if each pair of values is equal both take constant space, so they do not contribute to the overall space complexity of the code.
