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 listtest_list = [1, 7, 5, 6, 3, 8]# initializing kk = 4# printing list print ("The list : " + str(test_list))# using naive method # Maximum element till K valueres = 0for 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 listtest_list = [1, 7, 5, 6, 3, 8]# initializing kk = 4# printing list print ("The list : " + str(test_list))# using list comprehension# Maximum element till K valueres = 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 listlst = [3, 5, 2, 8, 1, 9, 4]#inputk = 5#k valuemax_val = max_element_till_k(lst, k)#max valueprint(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
