Given a list, a new list is constructed that has frequency of elements greater than or equal to it, corresponding to each element of the list.
Input : test_list = [6, 3, 7, 1, 2, 4]
Output : [2, 4, 1, 6, 5, 3]
Explanation : 6, 7 are greater or equal to 6 in list, hence 2.Input : test_list = [6, 3, 7]
Output : [2, 3, 1]
Explanation : 6, 7 are greater or equal to 6 in list, hence 2.
Method 1 : Using sum() and list comprehension
Here, nested list comprehension is used to access each element of the list and sum() is used to get summation of elements which are greater than or equal to the indexed element.
Python3
# initializing listtest_list = [6, 3, 7, 1, 2, 4]# printing original listprint("The original list is : " + str(test_list))# sum() performs counts of element which are Greater or equal to res = [sum(1 for ele in test_list if sub <= ele) for sub in test_list] # printing result print("Greater elements Frequency list : " + str(res)) |
The original list is : [6, 3, 7, 1, 2, 4] Greater elements Frequency list : [2, 4, 1, 6, 5, 3]
Time Complexity: O(n), where n is the length of the input list. This is because we’re using the built-in sum() and list comprehension which has a time complexity of O(n) in the worst case.
Auxiliary Space: O(1), as we’re not using additional space
Method 2 : Using sorted(), bisect_left() and list comprehension
In this, we get elements smaller than the element using bisect_left(). Then, subtracting the number so obtained from total length gives us count of elements greater than element.
Python3
# import moduleimport bisect# initializing listtest_list = [6, 3, 7, 1, 2, 4]# printing original listprint("The original list is : " + str(test_list))# sorting before bisect temp = sorted(test_list)# getting total greater elements for each elementres = [len(test_list) - bisect.bisect_left(temp, ele) for ele in test_list] # printing result print("Greater elements Frequency list : " + str(res)) |
The original list is : [6, 3, 7, 1, 2, 4] Greater elements Frequency list : [2, 4, 1, 6, 5, 3]
Method 3:Using a for loop and if statement
Python3
# initializing listtest_list = [6, 3, 7, 1, 2, 4]# printing original listprint("The original list is : " + str(test_list))# using for loop and if statementres = []for sub in test_list: count = 0 for ele in test_list: if sub <= ele: count += 1 res.append(count)# printing result print("Greater elements Frequency list : " + str(res))#This code is contributed by Vinay Pinjala. |
The original list is : [6, 3, 7, 1, 2, 4] Greater elements Frequency list : [2, 4, 1, 6, 5, 3]
Time complexity: O(n)
Auxiliary Space: O(n)
Method 4: Approach using a dictionary
Python3
# Initialize the list of numberstest_list = [6, 3, 7, 1, 2, 4]# Print the original listprint("The original list is : " + str(test_list))# Initialize an empty dictionary to store the count of elements greater than or equal to each elementcounts = {}# Loop through each element in the listfor i in test_list: # Calculate the count of elements greater than or equal to the current element counts[i] = len([j for j in test_list if j >= i])# Construct the final result list using the values in the counts dictionaryresult = [counts[i] for i in test_list]# Print the final result listprint("Greater elements Frequency list : " + str(result)) |
The original list is : [6, 3, 7, 1, 2, 4] Greater elements Frequency list : [2, 4, 1, 6, 5, 3]
Step-by-step algorithm:
- Initialize the list of numbers test_list with the given input.
- Initialize an empty dictionary counts to store the count of elements greater than or equal to each element.
- Loop through each element in the list using a for loop.
- Inside the loop, calculate the count of elements greater than or equal to the current element by using a list comprehension. The list comprehension creates a new list of all elements in test_list that are greater than or equal to the current element i, and the len() function is used to count the number of elements in the list.
- Add an entry to the counts dictionary for the current element i, with the count calculated in step 4 as the value.
- Construct the final result list by using a list comprehension to extract the count for each element in test_list from the counts dictionary.
- Print the final result list.
Time complexity:
The time complexity of the algorithm is O(n^2), where n is the length of the input list test_list. This is because the algorithm loops through each element in the list, and for each element, it loops through the entire list again to count the number of elements greater than or equal to the current element. Therefore, the total number of operations performed is proportional to n*n.
Auxiliary space complexity:
The auxiliary space complexity of the algorithm is O(n), where n is the length of the input list test_list. This is because the counts dictionary stores an entry for each element in the input list, and the size of the dictionary is proportional to n. The final result list also has n elements, so the space complexity of the algorithm is linear with respect to the length of the input list.
Method 5: Using recursion:
Algorithm:
1.We define a recursive function count_greater_or_equal_elements that takes in the list test_list, dictionaries counts, result, and integer i as parameters.
2.The function first checks if i is equal to the length of test_list. If it is, the function returns result.
3.Otherwise, the function calculates the count of elements greater than or equal to the current element current_element at index i in test_list.
4.The function stores this count in the counts dictionary with the current_element as key and count as value.
5.The function appends the count to the result list.
6.The function then recursively calls itself with the updated counts, result, and i values.
Python3
def count_greater_or_equal_elements(test_list, counts={}, result=[], i=0): # Base case: If all elements in the list have been processed, return the final result if i == len(test_list): return result # Recursive case: Calculate the count of elements greater than or equal to the current element current_element = test_list[i] count = len([j for j in test_list if j >= current_element]) counts[current_element] = count # Add the count to the result list result.append(count) # Recursively process the rest of the list return count_greater_or_equal_elements(test_list, counts, result, i+1) # Initialize the list of numberstest_list = [6, 3, 7, 1, 2, 4]# Print the original listprint("The original list is : " + str(test_list))# Call the recursive function to calculate the count of elements greater than or equal to each elementresult = count_greater_or_equal_elements(test_list)# Print the final result listprint("Greater elements Frequency list : " + str(result))#This code is contributed by Jyothi pinjala. |
The original list is : [6, 3, 7, 1, 2, 4] Greater elements Frequency list : [2, 4, 1, 6, 5, 3]
Time complexity:
The time complexity of the algorithm is O(n^2), where n is the length of the input list.
This is because for each element in the list, we need to compare it to every other element in the list to determine the count of elements greater than or equal to it. This results in a nested loop structure, giving a time complexity of O(n^2).
Auxiliary Space:
The space complexity of the algorithm is O(n), where n is the length of the input list.
This is because we need to create a dictionary counts with n key-value pairs to store the count of elements greater than or equal to each element in the list. We also need to create a list result of size n to store the result. Additionally, we use recursion which results in n function call stack frames. Therefore, the total space complexity is O(n).
Method 6: Using numpy
Step-by-step approach:
- Initialize an empty list “result” to store the frequency of greater elements for each element in the input list.
- Convert the input list “test_list” into a NumPy array.
- Loop through each element “x” in the input list “test_list“.
- Create a boolean NumPy array by comparing each element in the NumPy array with “x“.
- Calculate the sum of the boolean array using the NumPy “np.sum()” function to count the number of elements greater than or equal to “x“.
- Append the result to the “result” list.
- Return the “result” list.
Python3
import numpy as nptest_list = [6, 3, 7, 1, 2, 4]print("The original list is : " + str(test_list))result = [np.sum(np.array(test_list) >= x) for x in test_list]print("Greater elements Frequency list : " + str(result)) |
Output
The original list is : [6, 3, 7, 1, 2, 4] Greater elements Frequency list : [2, 4, 1, 6, 5, 3]
Time complexity: O(n^2) due to the nested loops in calculating the frequency for each element in the input list.
Auxiliary space: O(n) to store the “result” list.
