Sometimes, while working with Python Lists, we can have a problem in which we need to extract first K unique elements. This means we need to extract duplicate if they occur in first K elements as well. This can essentially make count of first K unique elements more than K. This kind of problem can have application in day-day programming. Let’s discuss certain ways in which this task can be performed.
Input : test_list = [6, 7, 6, 7], K = 2
Output : [6, 7]Input : test_list = [3, 4, 5, 7], K = 3
Output : [3, 4, 5]
Method #1 : Using loop This is brute force way in which this task can be performed. In this, we perform task of getting elements by keeping counter and store list to compare previous occurrences.
Python3
# Python3 code to demonstrate working of # First K unique elements# Using loop# initializing listtest_list = [6, 7, 6, 7, 8, 3, 9, 11]# printing original listprint("The original list is : " + str(test_list))# initializing K K = 4# First K unique elements# Using loopstore = []res = []cnt = 0for ele in test_list: if ele not in store: cnt = cnt + 1 store.append(ele) res.append(ele) if cnt >= K : break # printing result print("The extracted elements : " + str(res)) |
The original list is : [6, 7, 6, 7, 8, 3, 9, 11] The extracted elements : [6, 7, 6, 7, 8, 3]
Time complexity: O(n), where n is the length of the input list test_list.
Auxiliary Space: O(K), where K is the value of the variable K. The space used by the store list to store unique elements is proportional to the value of K. The space used by the res list is also proportional to the length of the input list, but it is not counted in the auxiliary space complexity because it is a required output of the program.
Method #2 : Using set() + filter() + lambda The combination of above functions can be used to solve this problem. In this, we perform the task of creating lookup list using set and filter() + lambda is used to check the values against list.
Python3
# Python3 code to demonstrate working of # First K unique elements# Using set() + filter() + lambda# initializing listtest_list = [6, 7, 6, 7, 8, 3, 9, 11]# printing original listprint("The original list is : " + str(test_list))# initializing K K = 4# First K unique elements# Using set() + filter() + lambdastore = set(list({ele for ele in test_list})[:K])res = list(filter(lambda ele: ele in store, test_list)) # printing result print("The extracted elements : " + str(res)) |
The original list is : [6, 7, 6, 7, 8, 3, 9, 11] The extracted elements : [6, 7, 6, 7, 8, 3]
Time complexity: The time complexity of this code is O(nlogn), where n is the length of the input list.
Auxiliary space: The auxiliary space complexity of this code is O(n), where n is the length of the input list.
