Queries to find the maximum and minimum array elements excluding elements from a given range | Function to find the maximum and minimum array elements up to the i - th index ; Traverse the array ; Compare current value with maximum and minimum values up to previous index ; Function to find the maximum and minimum array elements from i - th index ; Traverse the array in reverse ; Compare current value with maximum and minimum values in the next index ; Function to find the maximum and minimum array elements for each query ; If no index remains after excluding the elements in a given range ; Find maximum and minimum from from the range [ R + 1 , N - 1 ] ; Find maximum and minimum from from the range [ 0 , N - 1 ] ; Find maximum and minimum values from the ranges [ 0 , L - 1 ] and [ R + 1 , N - 1 ] ; Print maximum and minimum value ; Function to perform queries to find the minimum and maximum array elements excluding elements from a given range ; Size of the array ; Size of query array ; prefix [ i ] [ 0 ] : Stores the maximum prefix [ i ] [ 1 ] : Stores the minimum value ; suffix [ i ] [ 0 ] : Stores the maximum suffix [ i ] [ 1 ] : Stores the minimum value ; Function calls to store maximum and minimum values for respective ranges ; Driver Code ; Given array
def prefixArr ( arr , prefix , N ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT if ( i == 0 ) : NEW_LINE INDENT prefix [ i ] [ 0 ] = arr [ i ] NEW_LINE prefix [ i ] [ 1 ] = arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT prefix [ i ] [ 0 ] = max ( prefix [ i - 1 ] [ 0 ] , arr [ i ] ) NEW_LINE prefix [ i ] [ 1 ] = min ( prefix [ i - 1 ] [ 1 ] , arr [ i ] ) NEW_LINE DEDENT DEDENT return prefix NEW_LINE DEDENT def suffixArr ( arr , suffix , N ) : NEW_LINE INDENT for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( i == N - 1 ) : NEW_LINE INDENT suffix [ i ] [ 0 ] = arr [ i ] NEW_LINE suffix [ i ] [ 1 ] = arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT suffix [ i ] [ 0 ] = max ( suffix [ i + 1 ] [ 0 ] , arr [ i ] ) NEW_LINE suffix [ i ] [ 1 ] = min ( suffix [ i + 1 ] [ 1 ] , arr [ i ] ) NEW_LINE DEDENT DEDENT return suffix NEW_LINE DEDENT def maxAndmin ( prefix , suffix , N , L , R ) : NEW_LINE INDENT maximum , minimum = 0 , 0 NEW_LINE if ( L == 0 and R == N - 1 ) : NEW_LINE INDENT print ( " No ▁ maximum ▁ and ▁ minimum ▁ value " ) NEW_LINE return NEW_LINE DEDENT elif ( L == 0 ) : NEW_LINE INDENT maximum = suffix [ R + 1 ] [ 0 ] NEW_LINE minimum = suffix [ R + 1 ] [ 1 ] NEW_LINE DEDENT elif ( R == N - 1 ) : NEW_LINE INDENT maximum = prefix [ L - 1 ] [ 0 ] NEW_LINE minimum = prefix [ R - 1 ] [ 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT maximum = max ( prefix [ L - 1 ] [ 0 ] , suffix [ R + 1 ] [ 0 ] ) NEW_LINE minimum = min ( prefix [ L - 1 ] [ 1 ] , suffix [ R + 1 ] [ 1 ] ) NEW_LINE DEDENT print ( maximum , minimum ) NEW_LINE DEDENT def MinMaxQueries ( a , queries ) : NEW_LINE INDENT N = len ( arr ) NEW_LINE q = len ( queries ) NEW_LINE prefix = [ [ 0 for i in range ( 2 ) ] for i in range ( N ) ] NEW_LINE suffix = [ [ 0 for i in range ( 2 ) ] for i in range ( N ) ] NEW_LINE prefix = prefixArr ( arr , prefix , N ) NEW_LINE suffix = suffixArr ( arr , suffix , N ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT L = queries [ i ] [ 0 ] NEW_LINE R = queries [ i ] [ 1 ] NEW_LINE maxAndmin ( prefix , suffix , N , L , R ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 1 , 8 , 3 , 5 , 7 , 4 ] NEW_LINE queries = [ [ 4 , 6 ] , [ 0 , 4 ] , [ 3 , 7 ] , [ 2 , 5 ] ] NEW_LINE MinMaxQueries ( arr , queries ) NEW_LINE DEDENT