One of the problem that is basically a subproblem for many complex problems, finding maximum number till a certain number in list in python, is commonly encountered and this particular article discusses possible solutions to this particular problem. Method #1 : Naive method The most common way this problem can be solved is using a loop and just max the occurrences of elements that are till given number K.
Python3
# Python 3 code to demonstrate # Maximum element till K value # using naive method # initializing list test_list = [ 1 , 7 , 5 , 6 , 3 , 8 ] # initializing k k = 4 # printing list print ("The list : " + str (test_list)) # using naive method # Maximum element till K value res = 0 for i in test_list : if i < = k : res = max (res, i) # printing the intersection print ("The maximum number till K : " + str (res)) |
The list : [1, 7, 5, 6, 3, 8] The maximum number till K : 3
Time complexity: O(n), where n is the length of the test_list.
Auxiliary Space: O(1), constant extra space is required
Method #2 : Using list comprehension This method achieves this task in a similar way, but in a more concise manner. List comprehension always lowers the lines of codes in the program even though runs a similar approach in the background.
Python3
# Python 3 code to demonstrate # Maximum element till K value # using list comprehension # initializing list test_list = [ 1 , 7 , 5 , 6 , 3 , 8 ] # initializing k k = 4 # printing list print ("The list : " + str (test_list)) # using list comprehension # Maximum element till K value res = max ([i for i in test_list if i < = k]) # printing the intersection print ("The maximum number till K : " + str (res)) |
The list : [1, 7, 5, 6, 3, 8] The maximum number till K : 3
Time complexity: O(n), where n is the length of the test_list.
Auxiliary Space: O(1), constant extra space is required
Method #3 : Using sorted()
Approach
Sort the list in descending order and then take the Kth element from the sorted list.
Step-by-step algorithm
1. Define a function called max_element_till_k that takes two arguments: a list and an integer K.
2. Slice the list to get the first K elements, and store it in a variable called sliced_list.
3. Sort the sliced_list in descending order using the sorted() function with the reverse=True argument, and store it in a variable called sorted_list.
4. Return the first element of the sorted_list using index notation, which will be the maximum element in the list till the K value.
Python3
def max_element_till_k(lst, k): #define list and k sorted_list = sorted (lst[:k], reverse = True ) #sort the list upto k value return sorted_list[ 0 ] # get the maximum element in sorted list lst = [ 3 , 5 , 2 , 8 , 1 , 9 , 4 ] #input k = 5 #k value max_val = max_element_till_k(lst, k) #max value print (max_val) #print output |
8
Time complexity: O(klogk), where k is the upper limit of the range in which the maximum number has to be found
Space complexity: O(k), where k is the upper limit of the range in which the maximum number has to be found