Longest subarray having average greater than or equal to x | Function to find index in preSum list of tuples upto which all prefix sum values are less than or equal to val . ; Starting and ending index of search space . ; To store required index value ; If middle value is less than or equal to val then index can lie in mid + 1. . n else it lies in 0. . mid - 1 ; Function to find Longest subarray having average greater than or equal to x . ; Update array by subtracting x from each element ; Length of Longest subarray . ; list to store pair of prefix sum and corresponding ending index value . ; To store current value of prefix sum . ; To store minimum index value in range 0. . i of preSum vector . ; Insert values in preSum vector ; Update minInd array . ; If sum is greater than or equal to 0 , then answer is i + 1 ; If sum is less than 0 , then find if there is a prefix array having sum that needs to be added to current sum to make its value greater than or equal to 0. If yes , then compare length of updated subarray with maximum length found so far ; Driver Code
def findInd ( preSum , n , val ) : NEW_LINE INDENT l = 0 NEW_LINE h = n - 1 NEW_LINE ans = - 1 NEW_LINE while ( l <= h ) : NEW_LINE INDENT mid = ( l + h ) // 2 NEW_LINE if preSum [ mid ] [ 0 ] <= val : NEW_LINE INDENT ans = mid NEW_LINE l = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT h = mid - 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def LongestSub ( arr , n , x ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT arr [ i ] -= x NEW_LINE DEDENT maxlen = 0 NEW_LINE preSum = [ ] NEW_LINE total = 0 NEW_LINE minInd = [ None ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT total += arr [ i ] NEW_LINE preSum . append ( ( total , i ) ) NEW_LINE DEDENT preSum = sorted ( preSum ) NEW_LINE minInd [ 0 ] = preSum [ 0 ] [ 1 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT minInd [ i ] = min ( minInd [ i - 1 ] , preSum [ i ] [ 1 ] ) NEW_LINE DEDENT total = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT total += arr [ i ] NEW_LINE if total >= 0 : NEW_LINE INDENT maxlen = i + 1 NEW_LINE DEDENT else : NEW_LINE INDENT ind = findInd ( preSum , n , total ) NEW_LINE if ( ind != - 1 ) & ( minInd [ ind ] < i ) : NEW_LINE INDENT maxlen = max ( maxlen , i - minInd [ ind ] ) NEW_LINE DEDENT DEDENT DEDENT return maxlen NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ - 2 , 1 , 6 , - 3 ] NEW_LINE n = len ( arr ) NEW_LINE x = 3 NEW_LINE print ( LongestSub ( arr , n , x ) ) NEW_LINE DEDENT