Python | Minimum K records of Nth index in tuple list

Sometimes, while working with data, we can have a problem in which we need to get the minimum of elements filtered by the Nth element of record. This has a very important utility in web development domain. Let’s discuss certain ways in which this task can be performed. 

Method #1 : Using filter() + lambda + set() + list comprehension The combination of above functions can be used to perform this particular function. In this, we first filter the min K elements from Nth index and then apply this values to the list and return the result. 

Time Complexity: O(n)
Auxiliary Space: O(n)

Method #2 : Using groupby() + sorted() + loop This task can also be performed using above functionalities. In this, we first group the min K elements together and then limit by K while constructing the result list. 

The time complexity of the given code is O(NlogN + K), where N is the length of the input list and K is the number of minimum elements required.
The auxiliary space complexity of the given code is O(N), where N is the length of the input list. 

Method #3: Using sorted() and slicing

Step-by-step algorithm:

1. Initialize the input list and print it.
2. Initialize N and K.
3. Sort the input list by the Nth index in ascending order.
4. Select the first K elements from the sorted list using slicing.
5. Print the resulting list.

The original list is : [('gfg', 4, 'good'), ('gfg', 2, 'better'), ('gfg', 1, 'best'), ('gfg', 3, 'neveropen')]
Min K elements of Nth index are : [('gfg', 1, 'best'), ('gfg', 2, 'better')]

Time complexity: The time complexity of the sorted() function is O(nlogn), where n is the length of the input list. Slicing a list takes O(k) time where k is the number of elements to slice. Therefore, the time complexity of this approach is O(nlogn + k)
Auxiliary space: O(1).

Method #4: Using heapq.nsmallest()

Step-by-step approach:

• Initialize a list of tuples test_list with some values.
• Print the original list using the print() function.
• Initialize variables N and K with values of 1 and 2, respectively.
• Use the heapq.nsmallest() function to find the minimum K records of the Nth index in the tuple list. The heapq.nsmallest() function takes three arguments: K, the list to find minimum from, and a key function to determine the ordering of elements in the list.
• The key parameter is a lambda function that returns the Nth element of each tuple in test_list.
• Store the result in the variable res.
• Print the result using the print() function.

Below is the implementation of the above approach:

The original list is : [('gfg', 4, 'good'), ('gfg', 2, 'better'), ('gfg', 1, 'best'), ('gfg', 3, 'neveropen')]
Min K elements of Nth index are : [('gfg', 1, 'best'), ('gfg', 2, 'better')]

Time complexity: O(N log K), where N is the length of the list and K is the number of minimum elements to find.
Auxiliary space: O(K), as only the K minimum elements are stored in the res variable.

Method 5: Using a loop and a dictionary

This method involves iterating over the list of tuples and creating a dictionary where the keys are the Nth elements of each tuple, and the values are lists containing the tuples with that Nth element. We then extract the K lowest records by iterating over the keys of the dictionary in sorted order and appending the K lowest tuples from each corresponding value list to a result list.

Step-by-step approach:

• Initialize the variables N and K with the values of the Nth element we want to extract and the number of lowest records we want to extract, respectively.
• Initialize an empty dictionary named temp_dict to store the tuples with the same Nth element.
• Iterate over the test_list using a for loop, and for each tuple:
  • Get the Nth element of the tuple using tuple[N] and store it in a variable named key.
  • Check if key is already a key in temp_dict. If it is, append the tuple to the corresponding value list. If it isn’t, create a new key-value pair with key as the key and a new list containing the tuple as the value.
• Initialize an empty list named res to store the final result.
• Iterate over the keys of temp_dict in sorted order, and for each key:
  • Extract the K lowest tuples from the corresponding value list using list slicing, and append them to res.
  • If the length of res is equal to or greater than K, break out of the loop.
• Print the result using the print() function.

Below is the implementation of the above approach:

The original list is : [('gfg', 4, 'good'), ('gfg', 2, 'better'), ('gfg', 1, 'best'), ('gfg', 3, 'neveropen')]
Min K elements of Nth index are : [('gfg', 1, 'best'), ('gfg', 2, 'better')]

Time complexity: O(N log N) for sorting the dictionary keys and values, where N is the length of the input list.
Auxiliary space: O(N) for storing the dictionary.

Method 6: Using reduce():

Algorithm:

1. Initialize the list test_list and print it.
2. Initialize N and K values.
3. Sort the test_list based on the Nth index using sorted() method and slice the sorted list to get only the first K elements.
4. Use the reduce() method and a lambda function to iterate through the sliced list and add the elements to the
5. accumulator if the Nth index is not already present in the accumulator.
6. The final value of the accumulator will be the required output.
7. Print the res list.

The original list is : [('gfg', 4, 'good'), ('gfg', 2, 'better'), ('gfg', 1, 'best'), ('gfg', 3, 'neveropen')]
Min K elements of Nth index are : [('gfg', 1, 'best'), ('gfg', 2, 'better')]

Time Complexity: O(N log N + K) (due to sorting and iteration through the list of length K)

Added another approach  (the size of the output list)