Sometimes, while working with Python lists, we can have a problem in which we wish to find N largest elements. This task can occur in many domains such as web development and while working with Databases. We might sometimes, require to just find the indices of them. Let’s discuss a certain way to find indices of N largest elements in the list.
Method 1: Using sorted() + lambda + list slicing This task can be performed using the combination of the above functions. In this, the sorted(), can be used to get the container in a way that requires getting N largest elements at the rear end, and then the indices can be computed using list slicing.
Python3
# Python3 code to demonstrate working of# Indices of N largest elements in list# using sorted() + lambda + list slicing# initialize listtest_list = [5, 6, 10, 4, 7, 1, 19]# printing original listprint("The original list is : " + str(test_list))# initialize N N = 4# Indices of N largest elements in list# using sorted() + lambda + list slicingres = sorted(range(len(test_list)), key = lambda sub: test_list[sub])[-N:]# printing resultprint("Indices list of max N elements is : " + str(res)) |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of max N elements is : [1, 4, 2, 6]
Time complexity: O(n log n) due to the sorting function used in the code.
Auxiliary space: O(n) as an additional list of indices is created to store the indices of the N largest elements.
Method 2: Using extend(),sort() and index() methods
Python3
# Python3 code to demonstrate working of# Indices of N largest elements in list# initialize listtest_list = [5, 6, 10, 4, 7, 1, 19]# printing original listprint("The original list is : " + str(test_list))# initialize NN = 4# Indices of N largest elements in listx = []x.extend(test_list)x.sort(reverse=True)a = x[:N]res = []for i in a: res.append(test_list.index(i))res.sort()# printing resultprint("Indices list of max N elements is : " + str(res)) |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of max N elements is : [1, 2, 4, 6]
Time complexity: O(n*logn) where n is the length of the input list.
Auxiliary space: O(n), as the “x” and “res” lists have the same length as the input list, and the “a” list has a maximum length of N.
Method #3: Using heapq.nlargest()
The heapq library’s nlargest() function can be used to find the N largest elements in a list and then the index() method can be used to find the indices of those elements. Time complexity of this method is O(n log k) where n is the size of the list and k is the value of N. Space complexity is O(k) as we are storing the N largest elements in a heap.
Python3
# Python3 code to demonstrate working of# Indices of N largest elements in list# using heapq.nlargest()# importing heapqimport heapq# initialize listtest_list = [5, 6, 10, 4, 7, 1, 19]# printing original listprint("The original list is : " + str(test_list))# initialize NN = 4# Indices of N largest elements in list# using heapq.nlargest()res = [test_list.index(i) for i in heapq.nlargest(N, test_list)]# printing resultprint("Indices list of max N elements is : " + str(res[::-1]))#This code is contributed by Edula Vinay Kumar Reddy |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of max N elements is : [1, 4, 2, 6]
Time Complexity: O(n), where n is the length of the list test_list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list
Method #4: Using itertools.islice()
Algorithm:
- Initialize the list and the value of N.
- Sort the list in decreasing order.
- Create an empty result list.
- Iterate through the original list and check if the element exists in the first N elements of the sorted list.
- If it exists, append its index to the result list.
- Return the result list.
Python3
# Python3 code to demonstrate working of# Indices of N largest elements in listimport itertools# initialize listtest_list = [5, 6, 10, 4, 7, 1, 19]# printing original listprint("The original list is : " + str(test_list))# initialize NN = 4# Indices of N largest elements in listsorted_list = sorted(test_list, reverse=True)res = [i for i,x in enumerate(test_list) if x in itertools.islice(sorted_list, N)]# printing resultprint("Indices list of max N elements is : " + str(res)) |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of max N elements is : [1, 2, 4, 6]
Time complexity: O(n log n) for sorting the list, followed by O(n) for iterating through the list and checking the existence of elements in the sorted list, resulting in a final time complexity of O(n log n).
Auxiliary Space: O(n) for the result list.
