Python program to find N largest elements from a list

Given a list of integers, the task is to find N largest elements assuming size of list is greater than or equal o N. 

Examples :

Input : [4, 5, 1, 2, 9] 
        N = 2
Output :  [9, 5]

Input : [81, 52, 45, 10, 3, 2, 96] 
        N = 3
Output : [81, 96, 52]

A simple solution traverse the given list N times. In every traversal, find the maximum, add it to result, and remove it from the list. Below is the implementation : 

[85, 41]

Output :

[85, 41]

Time Complexity: O(N * size) where size is size of the given list. 
Auxiliary space: O(N)

Method 2: 

[298, 900, 1000, 3579]

Output:

[-45, 100, 200, 298, 900, 1000, 3579]
Find the N largest element: 4
[298, 900, 1000, 3579]

Time Complexity: O(nlogn)

Auxiliary Space: O(1)

Method 3: Using sort() and loop

Approach:

1. Sort the given list
2. Traverse the list up to N values and append elements in new array arr.
3. Print the array arr.

[298, 900, 1000, 3579]

Time Complexity: O(n*logn)
Auxiliary Space: O(n), where n is length of list.

Please refer k largest(or smallest) elements in an array for more efficient solutions of this problem.

Approach #4: Using heapq

Initialize a heap queue using the input list. Use the heapq.nlargest() function to find the N largest elements in the heap queue. Return the result.

Algorithm

1. Initialize a heap queue using the input list.
2. Use the heapq.nlargest() function to find the N largest elements in the heap queue.
3. Return the result.

[9, 5]
[96, 81, 52]

Time complexity: O(n log n), where n is the length of the input list due to building the heap.
Auxiliary Space: O(n), where n is the length of the input list, due to the heap queue.

Using numpy.argsort() function

note: install numpy module using command “pip install numpy”

Algorithm:

Convert the given list into a numpy array using np.array() function.
Use np.argsort() function to get the indices of the sorted numpy array in ascending order.
Use negative indexing and extract the last N indices from the sorted array.
Use the extracted indices to get the corresponding elements from the original numpy array.
Return the N maximum elements from the original list.

Output:

[10 41 85]
 

Time complexity:

Converting list to numpy array takes O(n) time, where n is the length of the list.
Sorting the numpy array using np.argsort() function takes O(nlogn) time.
Extracting the last N indices using negative indexing takes O(1) time.
Extracting the N maximum elements from the original list takes O(N) time.
Overall time complexity is O(nlogn).
 

Auxiliary Space:

The additional space required is to store the numpy array which takes O(n) space. Therefore, the space complexity is O(n).

Method : Using Sorted() + loop

Algorithm :

1. A list of integers named “list” is initialized with the values [2, 1, 8, 7, 3, 0, 9, 4].
2. An integer variable named “n” is initialized with the value 3. This variable specifies how many largest elements should be retrieved from the list.
3. Two empty list variables, “res” and “list1”, are initialized.
4. The original list is printed using the print() function and the “list” variable.
5. The sorted() function is used to sort the list in descending order, and the sorted list is assigned to the “list1” variable.
6. A for loop is used to iterate from 0 to n-1, and the first n elements of the sorted list are appended to the “res” list using the append() method.
7. The sorted list is printed using the print() function and the “list1” variable.
8. The n largest elements in the list are printed using the print() function, the number “n”, and the “res” list.

The given list is: [2, 1, 8, 7, 3, 0, 9, 4]
The sorted list is: [9, 8, 7, 4, 3, 2, 1, 0]
The  3  largest elements in the given list are: [9, 8, 7]

Time Complexity : O(n log n)

Auxiliary Space : O(n)