Largest subarray having sum greater than k | Comparison function used to sort preSum vector . ; Function to find index in preSum vector 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 largest subarray having sum greater than or equal to k . ; Length of largest subarray . ; Vector to store pair of prefix sum and corresponding ending index value . ; To store the 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 k , then answer is i + 1. ; If sum is less than or equal to k , then find if there is a prefix array having sum that needs to be added to current sum to make its value greater than k . If yes , then compare length of updated subarray with maximum length found so far . ; Driver code .
def compare ( a , b ) : NEW_LINE INDENT if a [ 0 ] == b [ 0 ] : NEW_LINE INDENT return a [ 1 ] < b [ 1 ] NEW_LINE DEDENT return a [ 0 ] < b [ 0 ] NEW_LINE DEDENT def findInd ( preSum , n , val ) : NEW_LINE INDENT l , h = 0 , 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 largestSub ( arr , n , k ) : NEW_LINE INDENT maxlen = 0 NEW_LINE preSum = [ ] NEW_LINE Sum = 0 NEW_LINE minInd = [ None ] * ( n ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT Sum = Sum + arr [ i ] NEW_LINE preSum . append ( [ Sum , i ] ) NEW_LINE DEDENT preSum . sort ( ) 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 Sum = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT Sum = Sum + arr [ i ] NEW_LINE if Sum > k : NEW_LINE INDENT maxlen = i + 1 NEW_LINE DEDENT else : NEW_LINE INDENT ind = findInd ( preSum , n , Sum - k - 1 ) NEW_LINE if ind != - 1 and 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 k = 5 NEW_LINE print ( largestSub ( arr , n , k ) ) NEW_LINE DEDENT