The test for a monotonic sequence is a utility that has manifold applications in mathematics and hence every sphere related to mathematics. As mathematics and Computer Science generally go parallel, mathematical operations such as checking for strictly decreasing sequences can be useful to gather knowledge. Let us discuss certain ways to perform this test.
Method #1: Using all() + zip() The all() generally checks for all the elements fed to it. The task of zip() is to link list beginning from the beginning and list beginning from the first element, so that a check can be performed on all elements.
Python3
# Python 3 code to demonstrate # Test for strictly decreasing list# using zip() + all()# initializing listtest_list = [10, 8, 7, 5, 4, 1]# printing original listsprint ("Original list : " + str(test_list))# using zip() + all()# Test for strictly decreasing listres = all(i > j for i, j in zip(test_list, test_list[1:]))# printing resultprint ("Is list strictly decreasing ? : " + str(res)) |
Original list : [10, 8, 7, 5, 4, 1] Is list strictly decreasing ? : True
Time Complexity: O(n)
Auxiliary Space: O(1)
Method #2: Using reduce() + lambda reduce() coupled with lambda can also perform this task of checking for monotonicity. reduce function is used to cumulate the result as True or False, lambda function checks for each index value with next index value.
Python3
# Python 3 code to demonstrate # Test for strictly decreasing list# using reduce() + lambda# initializing listtest_list = [10, 8, 7, 5, 4, 1]# printing original listsprint ("Original list : " + str(test_list))# using reduce() + lambda# Test for strictly decreasing listres = bool(lambda test_list: reduce(lambda i, j: j if i > j else 9999, test_list) != 9999)# printing resultprint ("Is list strictly decreasing ? : " + str(res)) |
Original list : [10, 8, 7, 5, 4, 1] Is list strictly decreasing ? : True
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(1), as the function uses only constant amount of extra space.
Method #3: Using sort() and extend() methods
Python3
# Python3 code to demonstrate # to check for strictly decreasing list# initializing listtest_list = [10, 8, 7, 5, 4, 1]# printing original listsprint ("Original list : " + str(test_list))# to check for strictly decreasing listres=Falsex=[]x.extend(test_list)test_list.sort(reverse=True)if(x==test_list): res=True# printing resultprint ("Is list strictly decreasing ? : " + str(res)) |
Original list : [10, 8, 7, 5, 4, 1] Is list strictly decreasing ? : True
Time Complexity: O(n*logn), where n is the length of the input list.
Auxiliary Space: O(n), where n is the length of the input list.
Method #4: Use the numpy library
Use numpy.diff to calculate the difference between consecutive elements of the list, and then check if all the differences are negative. If all the differences are negative, then the list is strictly decreasing.
Python3
import numpy as np# initializing listtest_list = [10, 8, 7, 5, 4, 1]# printing original listsprint("Original list : " + str(test_list))# using numpy.diff()# Test for strictly decreasing listdiff_list = np.diff(test_list)res = np.all(diff_list < 0)# printing resultprint("Is list strictly decreasing? : " + str(res)) |
Output:
Original list : [10, 8, 7, 5, 4, 1] Is list strictly decreasing? : True
Time complexity: O(n), where n is the length of the list.
Auxiliary space: O(1)
Method #5: Using a loop
Use a loop to iterate through the list and check if each element is less than the previous one. If any element is greater than or equal to the previous one, then the list is not strictly decreasing.
Python3
test_list = [10, 8, 7, 5, 4, 1]# Initialize a boolean variable to Trueis_strictly_decreasing = True# Loop through the list starting from the second elementfor i in range(1, len(test_list)): # Check if the current element is greater than or equal to the previous one if test_list[i] >= test_list[i-1]: # If it is, set the boolean variable to False and break out of the loop is_strictly_decreasing = False break# Print the resultprint("Is list strictly decreasing? : " + str(is_strictly_decreasing)) |
Is list strictly decreasing? : True
Time complexity: O(n), where n is the length of the input list. This is because we only need to iterate through the list once to check if it’s strictly decreasing.
Auxiliary space: O(1), meaning that we don’t need to use any extra space beyond what’s required to store the input list and a few variables. This is because we’re not creating any additional data structures or making any recursive function calls.
Method 6: Using recursion
- Define a function is_strictly_decreasing(lst, n) that takes a list and its length as input.
- If the length of the list is 1, return True.
- If the last element of the list is greater than or equal to the second-last element, return False.
- Otherwise, call the same function recursively with the list without the last element and its length decremented by 1.
- Implement the above approach in code.
Python3
def is_strictly_decreasing(lst, n): if n == 1: return True if lst[n-1] >= lst[n-2]: return False return is_strictly_decreasing(lst, n-1)test_list = [10, 8, 7, 5, 4, 1]is_strictly_decreasing = is_strictly_decreasing(test_list, len(test_list))print("Is list strictly decreasing? : " + str(is_strictly_decreasing)) |
Is list strictly decreasing? : True
Time complexity: O(n), where n is the length of the list.
Auxiliary space: O(n), where n is the length of the list due to the recursion stack.
