Python | Top N pairs by Kth element from list

0 0 3 minutes read

Sometimes, while working with data, we can have a problem in which we need to get the maximum of elements filtered by the Kth 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 top N elements from Kth index and then apply these values to the list and return the result.

Python3

# Python3 code to demonstrate working of 
# Top N pairs by Kth element from list 
# Using filter() + lambda + set() + list comprehension 
 
# initialize list 
test_list = [('gfg', 4, 'good'), ('gfg', 2, 'better'), 
            ('gfg', 1, 'best'), ('gfg', 3, 'zambiatek')] 
 
# printing original list 
print("The original list is : " + str(test_list)) 
 
# initialize N 
N = 3
 
# initialize K 
K = 1
 
# Top N pairs by Kth element from list 
# Using filter() + lambda + set() + list comprehension 
temp = set(list({sub[K] for sub in test_list})[-N:]) 
res = list(filter(lambda sub: sub[K] in temp, test_list)) 
 
# printing result 
print("Top N elements of Kth index are : " + str(res)) 

Output

The original list is : [('gfg', 4, 'good'), ('gfg', 2, 'better'), ('gfg', 1, 'best'), ('gfg', 3, 'zambiatek')]
Top N elements of Kth index are : [('gfg', 4, 'good'), ('gfg', 2, 'better'), ('gfg', 3, 'zambiatek')]

Time Complexity: O(n*nlogn) where n is the number of elements in the list “test_list”. filter() + lambda + set() + list comprehension performs n*nlogn number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list

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

Python3

# Python3 code to demonstrate working of 
# Top N pairs by Kth element from list 
# Using groupby() + sorted() + loop 
import itertools 
 
# initialize list 
test_list = [('gfg', 4, 'good'), ('gfg', 2, 'better'), 
            ('gfg', 1, 'best'), ('gfg', 3, 'zambiatek')] 
 
# printing original list 
print("The original list is : " + str(test_list)) 
 
# initialize N 
N = 3
 
# initialize K 
K = 1
 
# Top N pairs by Kth element from list 
# Using groupby() + sorted() + loop 
res = [] 
temp = itertools.groupby(sorted(test_list, key = lambda sub : sub[K], 
                        reverse = True), key = lambda sub : sub[K]) 
for i in range(N): 
    res.extend(list(next(temp)[K])) 
 
# printing result 
print("Top N elements of Kth index are : " + str(res)) 

Output

The original list is : [('gfg', 4, 'good'), ('gfg', 2, 'better'), ('gfg', 1, 'best'), ('gfg', 3, 'zambiatek')]
Top N elements of Kth index are : [('gfg', 4, 'good'), ('gfg', 3, 'zambiatek'), ('gfg', 2, 'better')]

Time Complexity: O(n*nlogn), 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 #3: Using heapq.nlargest()

This approach uses the heapq.nlargest() function to get the top N elements from the list based on the Kth element. It is more efficient than the above two methods as it uses a heap data structure to find the top N elements in O(nlogk) time complexity.

Python3

import heapq
 
# initialize list 
test_list = [('gfg', 4, 'good'), ('gfg', 2, 'better'), ('gfg', 1, 'best'), ('gfg', 3, 'zambiatek')]
 
# printing original list
print("The original list is : " + str(test_list))
   
# initialize N 
N = 3
   
# initialize K 
K = 2
 
# Top N pairs by Kth element from list
# Using heapq.nlargest()
res = heapq.nlargest(N, test_list, key=lambda x: x[K])
 
# printing result
print("Top N elements of Kth index are : " + str(res))
#This code is contributed by Edula Vinay Kumar Reddy

Output

The original list is : [('gfg', 4, 'good'), ('gfg', 2, 'better'), ('gfg', 1, 'best'), ('gfg', 3, 'zambiatek')]
Top N elements of Kth index are : [('gfg', 4, 'good'), ('gfg', 3, 'zambiatek'), ('gfg', 2, 'better')]

The time complexity of this method is O(nlogk) and Auxiliary space is O(k).