Sometimes, while working with Python lists, we can have a problem in which we wish to find the indices for K smallest 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 K smallest elements in list.
Method 1: Using sorted() + lambda + list slicing
This task can be performed using a combination of the above functions. In this the sorted(), can be used to get the container in a way that requires to get K smallest elements at front end and then the indices can be computed using list slicing.
Python3
# Python3 code to demonstrate working of# Smallest K elements indices# 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 KK = 3# Smallest K elements indices# using sorted() + lambda + list slicingres = sorted(range(len(test_list)), key=lambda sub: test_list[sub])[:K]# Printing resultprint("Indices list of min K elements is : " + str(res)) |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of min K elements is : [5, 3, 0]
Time complexity: O(nlogn) (sorting using sorted() function)
Auxiliary space: O(n) (creating a sorted list of indices)
Method 2: using the heapq module
In this method to obtain the indices of the smallest K elements in a list can be to use the heapq module in Python. The heapq module provides the implementation of heap queue algorithm. We can use the nsmallest() function from the heapq module to find the smallest K elements and their indices in a list.
Python3
import heapq# Initialize listtest_list = [5, 6, 10, 4, 7, 1, 19]# Printing original listprint("The original list is : " + str(test_list))# Initialize KK = 3# Smallest K elements indices using heapq modulesmallest_indices = heapq.nsmallest( K, range(len(test_list)), key=test_list.__getitem__)# Printing resultprint("Indices list of min K elements is : " + str(smallest_indices)) |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of min K elements is : [5, 3, 0]
Time complexity: O(n log K) where n is the length of the list test list and K is the number of smallest elements required.
Auxiliary space: O(K), which is the size of the heap that is created by the heapq nsmallest() function to store the smallest K elements.
Method 3: Using numpy.argsort() function
The algorithm used in this approach is the argsort function of the NumPy library. The argsort function returns the indices that would sort the input array in ascending order. We pass the input list to the argsort function to obtain an array of indices in ascending order.
Python3
import numpy as np# Input listtest_list = [5, 6, 10, 4, 7, 1, 19]# Printing original listprint("The original list is : " + str(test_list))# Initialize KK = 3# Smallest K elements indices# using numpy.argsort() functionres = np.argsort(test_list)[:K]# Printing resultprint("Indices list of min K elements is : " + str(list(res))) |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of min K elements is : [5, 3, 0]
Time complexity: O(n log n), where n is the length of the input list. This is because the argsort function uses the quicksort algorithm to sort the input list, which has an average time complexity of O(n log n).
Auxiliary space: O(N), as we are creating a new array to store the sorted indices.
Method 4: Using the bisect module:
Steps:
- Initialize a list test_list with some values and a variable K to a desired value.
- Create a list of indices indices using the range function and the length of the test_list.
- Sort the indices list based on the values in the test_list, using the sort method and a lambda function that takes an 4.index ‘i’ and returns the corresponding value in test_list[i].
- Take the first K indices from the sorted list to get the smallest_indices.
- Print the original list and the resulting smallest_indices list.
Python3
import bisect# Input list and valuetest_list = [5, 6, 10, 4, 7, 1, 19]K = 3# printing original listprint("The original list is : " + str(test_list))# Creating a list of indicesindices = list(range(len(test_list)))# Sorting indices based on values of test_listindices.sort(key=lambda i: test_list[i])# Getting the first K indices from the sorted listsmallest_indices = indices[:K]# printing resultprint("Indices list of min K elements is : " + str(smallest_indices))# This code is contributed by Vinay pinjala |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of min K elements is : [5, 3, 0]
Time complexity: O(n log n), where n is the length of the input list test_list. This is because the algorithm involves sorting the list of indices using the sort() method, which has a time complexity of O(n log n) in the average and worst case.
Auxiliary space: O(n) because it creates a list of indices of length n and a list of K smallest indices, which has a maximum length of K. Therefore, the overall space complexity is dominated by the list of indices of length n.
Method 5 : Using extend(),sort() and index() methods
Approach
- Create a new list with same elements of test_list using extend() method.
- Sort that list using sort() function.
- Slice the list till K index.
- Initiate a for loop to traverse sliced list and append index of element of sliced list in original list to an output list.
- Display output list.
Python3
# Python3 code to demonstrate working of# Smallest K elements indices# Initialize listtest_list = [5, 6, 10, 4, 7, 1, 19]# Printing original listprint("The original list is : " + str(test_list))# Initialize KK = 3# Smallest K elements indicesres = []x = []x.extend(test_list)x.sort()for i in x[:K]: res.append(test_list.index(i)) # printing resultprint("Indices list of min K elements is : " + str(res)) |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of min K elements is : [5, 3, 0]
Time complexity: O(n log n), where n is the length of the input list test_list. This is because the algorithm involves sorting the list of indices using the sort() method, which has a time complexity of O(n log n) in the average and worst case.
Auxiliary space: O(n) because it creates a list of indices of length n and a list of K smallest indices, which has a maximum length of K. Therefore, the overall space complexity is dominated by the list of indices of length n.
Method 6: Using loop
Steps:
- Initialize the list, test_list, and print it.
- Initialize the value of K and print it.
- Initialize an empty dictionary, index_dict, to store the indices and their corresponding values from test_list.
- Use a for loop to iterate through test_list, and add each element and its index to index_dict.
- Sort the dictionary index_dict by its values, which represent the elements of test_list.
- Create a list, smallest_indices, to store the indices of the smallest K elements.
- Use a for loop to iterate through the sorted index_dict and append the indices of the smallest K elements to the smallest_indices.
- Print the list of indices of the smallest K elements.
Python3
# Initialize listtest_list = [5, 6, 10, 4, 7, 1, 19]# Printing original listprint("The original list is : " + str(test_list))# Initialize KK = 3# Initializing dictionary to store indices and their corresponding valuesindex_dict = {}# Adding each element and its index to the dictionaryfor i, value in enumerate(test_list): index_dict[i] = value# Sort the dictionary by its values (the elements of test_list)sorted_dict = dict(sorted(index_dict.items(), key=lambda x: x[1]))# Create a list to store the indices of the smallest K elementssmallest_indices = []# Append the indices of the smallest K elements to the listfor i in range(K): smallest_indices.append(list(sorted_dict.keys())[i])# Printing resultprint("Indices list of min K elements is : " + str(smallest_indices)) |
The original list is : [5, 6, 10, 4, 7, 1, 19] Indices list of min K elements is : [5, 3, 0]
Time complexity: O(nlogn), where n is the length of test_list.
Auxiliary space: O(n) to store the dictionary index_dict and the sorted dictionary sorted_dict
