Given a list, our task is to write a Python program to remove all the non-increasing elements from the list.
Input : test_list = [5, 3, 4, 5, 7, 3, 9, 10, 3, 10, 12, 13, 3, 16, 1]
Output : [5, 5, 5, 7, 9, 10, 10, 12, 13, 16]
Explanation : 3, 4 are omitted as 5, (greater element) had occurred before them. Applies to all other omitted elements.
Input : test_list = [5, 3, 4, 5, 7, 3, 9]
Output : [5, 5, 5, 7, 9]
Explanation : 3, 4 are omitted as 5, (greater element) had occurred before them. Applies to all other omitted elements.
Method #1 : Using loop
In this, the previous element is checked before populating the further list, if the greater element is found, it’s appended, else it’s dropped using loop.
Python3
# Python3 code to demonstrate working of# Remove non-increasing elements# Using loop# initializing listtest_list = [5, 3, 4, 5, 7, 3, 9, 10, 3, 10, 12, 13, 3, 16, 1] # printing original listprint("The original list is : " + str(test_list))res = [test_list[0]]for ele in test_list: # checking preceding element to decide for greater element if ele >= res[-1]: res.append(ele) # printing resultprint("The list after removing non-increasing elements : " + str(res)) |
Output:
The original list is : [5, 3, 4, 5, 7, 3, 9, 10, 3, 10, 12, 13, 3, 16, 1]
The list after removing non-increasing elements : [5, 5, 5, 7, 9, 10, 10, 12, 13, 16]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2 : Using list comprehension + max + zip() + accumulate
In this, maximum elements are zipped till the current element, and then list comprehension is used to check if a higher element occurs than the current, if yes it’s added, else the new element is omitted from the result in runtime iteration.
Python3
# Python3 code to demonstrate working of# Remove non-increasing elements# Using list comprehension + max + zip() + accumulatefrom itertools import accumulate# initializing listtest_list = [5, 3, 4, 5, 7, 3, 9, 10, 3, 10, 12, 13, 3, 16, 1] # printing original listprint("The original list is : " + str(test_list))# checking for each element with curr maximum computed using zipres = [idx for idx, ele in zip(test_list, accumulate(test_list, max)) if idx == ele] # printing resultprint("The list after removing non-increasing elements : " + str(res)) |
Output:
The original list is : [5, 3, 4, 5, 7, 3, 9, 10, 3, 10, 12, 13, 3, 16, 1]
The list after removing non-increasing elements : [5, 5, 5, 7, 9, 10, 10, 12, 13, 16]
Time complexity: O(n*n), where n is the length of the test_list. The list comprehension + max + zip() + accumulate takes O(n*n) time
Auxiliary Space: O(n), extra space of size n is required
