While working with Python list, sometimes, we require to check for duplicates and may also sometimes require to track their indices. This kind of application can occur in day-day programming. Let’s discuss certain ways in which this problem can be solved.
Method #1 : Using loop + set() This task can be solved using the combination of above functions. In this, we just insert all the elements in set and then compare each element’s existence in actual list. If it’s the second occurrence or more, then index is added in result list.
Python3
# Python3 code to demonstrate working of# Duplicate element indices in list# Using set() + loop# initializing listtest_list = [1, 4, 5, 5, 5, 9, 1]# printing original listprint("The original list is : " + str(test_list))# Duplicate element indices in list# Using set() + loopoc_set = set()res = []for idx, val in enumerate(test_list): if val not in oc_set: oc_set.add(val) else: res.append(idx) # printing resultprint("The list of duplicate elements is : " + str(res)) |
The original list is : [1, 4, 5, 5, 5, 9, 1] The list of duplicate elements is : [3, 4, 6]
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(m), where m is the number of unique elements in the input list. This is because we use a set to keep track of the unique elements in the list, and the size of the set is at most equal to the number of unique elements. The additional space used by the program is the list res, which stores the indices of the duplicate elements. The worst-case scenario is when all the elements in the list are unique, in which case the space complexity is O(n).
Method #2: Using list comprehension + list slicing This method is one-liner alternative to perform this task. In this we just check for the non-repeating element using list slicing and keep adding index in case it’s repeated.
Python3
# Python3 code to demonstrate working of# Duplicate element indices in list# Using list comprehension + list slicing# initializing listtest_list = [1, 4, 5, 5, 5, 9, 1]# printing original listprint("The original list is : " + str(test_list))# Duplicate element indices in list# Using list comprehension + list slicingres = [idx for idx, val in enumerate(test_list) if val in test_list[:idx]] # printing resultprint("The list of duplicate elements is : " + str(res)) |
The original list is : [1, 4, 5, 5, 5, 9, 1] The list of duplicate elements is : [3, 4, 6]
Time complexity: O(n^2)
Auxiliary space: O(n)
Method #3: Using dictionary
Create a dictionary oc_dict to store the first occurrence of each element in the list along with its index. As iterating through the list, if encountered element is already in the dictionary, append its index to the res list.
Python3
# initializing listtest_list = [1, 4, 5, 5, 5, 9, 1]# printing original listprint("The original list is : " + str(test_list))# Duplicate element indices in list# Using dictionaryoc_dict = {}res = []for idx, val in enumerate(test_list): if val not in oc_dict: oc_dict[val] = idx else: res.append(idx)# printing resultprint("The list of duplicate elements is : " + str(res)) |
The original list is : [1, 4, 5, 5, 5, 9, 1] The list of duplicate elements is : [3, 4, 6]
Time complexity: O(N^2), where N is the length of the given list.
Auxiliary space: O(N)
