Python – Check whether the extracted element from each row of matrix can be in ascending order
Given a matrix, the task here is to first select an element from each row in such a manner that when taken in exact order they can potentially form a sorted list or a list in ascending order. If it is possible return True else False.
Input : test_list = [[3, 4, 6, 2], [3, 4, 9, 1], [8, 5, 4, 7], [9, 1, 2, 3]] Output : True Explanation : [2, 3, 4, 9] is possible increasing list.
Input : test_list = [[3, 4, 6, 2], [3, 4, 9, 1], [8, 5, 4, 7], [1, 1, 2, 3]] Output : False Explanation : Increasing list not possible.
In this, we keep updating the minimum possible element from each row, if the minimum element is greater than the previous element, the minimum is not found, and the result is flagged false indicating ascending list is not possible.
Example:
Python3
# Initializing list test_list = [[ 3 , 4 , 6 , 2 ], [ 3 , 4 , 9 , 1 ], [ 8 , 5 , 4 , 7 ], [ 9 , 1 , 2 , 3 ]] # Printing original list print ( "The original list is : " + str (test_list)) # Initializing with min of 1st row cur = min (test_list[ 0 ]) res = True for sub in test_list[ 1 :]: res = False # Checking row for greater than previous minimum for idx in sub: if idx > = cur: res = True # storing new minimum cur = idx break # Not there if not res: break # Printing result print ( "Is ascending list possible ? : " + str (res)) |
The original list is : [[3, 4, 6, 2], [3, 4, 9, 1], [8, 5, 4, 7], [9, 1, 2, 3]] Is ascending list possible ? : True
Time Complexity: O(n*m)
Auxiliary Space: O(n)
Method#2: Using Recursive method
The is_ascending_recursive function takes a matrix as input, along with an optional index variable i (which is initially set to 1) and a current minimum value cur. The function returns True if an ascending list is possible, and False otherwise.
The function first initializes the current minimum value as the minimum value in the first row. It then checks each subsequent row to see if it contains any values greater than or equal to the current minimum value. If it finds such a value, it recursively calls itself with the index of the next row and the new minimum value. If it reaches the end of the matrix without finding a suitable value, it returns False.
Python3
def is_ascending_recursive(matrix, i = 1 , cur = None ): if i = = len (matrix): return True # Initializing current minimum if cur is None : cur = min (matrix[ 0 ]) res = False # Checking row for greater than previous minimum for idx in matrix[i]: if idx > = cur: res = is_ascending_recursive(matrix, i + 1 , idx) if res: break return res # Initializing list test_list = [[ 3 , 4 , 6 , 2 ], [ 3 , 4 , 9 , 1 ], [ 8 , 5 , 4 , 7 ], [ 9 , 1 , 2 , 3 ]] # Printing original list print ( "The original list is : " + str (test_list)) # Initializing with min of 1st row res = is_ascending_recursive(test_list) # Printing result print ( "Is ascending list possible ? : " + str (res)) |
The original list is : [[3, 4, 6, 2], [3, 4, 9, 1], [8, 5, 4, 7], [9, 1, 2, 3]] Is ascending list possible ? : True
Time complexity: O(n^2), where n is the number of elements in the matrix. This is because the function may have to check each element in the matrix.
Auxiliary space: O(n), because the function uses recursion to explore the entire matrix, but only stores the current minimum value at each step.
Method 3: Using built-in zip() function
Python3
# Initializing list test_list = [[ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 9 , 10 , 11 , 12 ], [ 13 , 14 , 15 , 16 ]] # Printing original list print ( "The original list is : " + str (test_list)) # Initializing with min of 1st row cur = min (test_list[ 0 ]) res = True for sub in test_list[ 1 :]: # Checking row for greater than previous minimum if all (idx > = cur for idx in sub): # Storing new minimum cur = min (sub) else : res = False break # Printing result print ( "Is ascending list possible? : " + str (res)) |
The original list is : [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] Is ascending list possible? : True
Time complexity: O(nm), where n is the number of rows and m is the number of columns in the matrix.
Auxiliary space: O(nm) to store the transposed matrix.
Method 4: Using built-in map() and all() functions
- The map() function applies a lambda function to each sublist in the test_list. The lambda function checks if each element in the sublist is less than or equal to the next element in the sublist using the built-in zip() function. The result of the map() function is an iterator that produces a list of Boolean values, where each value represents whether the corresponding sublist is in ascending order or not.
- The all() function takes an iterable (in this case, the list of Boolean values produced by the map() function) and returns True if all the elements in the iterable are True, and False otherwise. Since we want to check if all sublists are in ascending order, we use all() to check if all the Boolean values in the list produced by map() are True.
Python3
# Initializing list test_list = [[ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 9 , 10 , 11 , 12 ], [ 13 , 14 , 15 , 16 ]] # Printing original list print ( "The original list is : " + str (test_list)) # Checking if each sublist is in ascending order res = all ( map ( lambda x: all (a < = b for a, b in zip (x, x[ 1 :])), test_list)) # Printing result print ( "Is ascending list possible? : " + str (res)) |
The original list is : [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] Is ascending list possible? : True
Time complexity: O(n^2), where n is the number of elements in the list of lists since we need to iterate over each element in each sublist.
Auxiliary space: O(1), since we only use a constant amount of memory to store the res variable.