Maximize length of subarray having equal elements by adding at most K | Function to find the maximum number of indices having equal elements after adding at most k numbers ; Sort the array in ascending order ; Make prefix sum array ; Initialize variables ; Update mid ; Check if any subarray can be obtained of length mid having equal elements ; Decrease max to mid ; Function to check if a subarray of length len consisting of equal elements can be obtained or not ; Sliding window ; Last element of the sliding window will be having the max size in the current window ; The current number of element in all indices of the current sliding window ; If the current number of the window , added to k exceeds totalNumbers ; Driver Code ; Function call
def maxEqualIdx ( arr , k ) : NEW_LINE INDENT arr . sort ( ) NEW_LINE prefixSum = [ 0 ] * ( len ( arr ) + 1 ) NEW_LINE prefixSum [ 1 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , len ( prefixSum ) - 1 , 1 ) : NEW_LINE INDENT prefixSum [ i + 1 ] = prefixSum [ i ] + arr [ i ] NEW_LINE DEDENT max = len ( arr ) NEW_LINE min = 1 NEW_LINE ans = 1 NEW_LINE while ( min <= max ) : NEW_LINE INDENT mid = ( max + min ) // 2 NEW_LINE if ( check ( prefixSum , mid , k , arr ) ) : NEW_LINE INDENT ans = mid NEW_LINE min = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT max = mid - 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def check ( pSum , lenn , k , a ) : NEW_LINE INDENT i = 0 NEW_LINE j = lenn NEW_LINE while ( j <= len ( a ) ) : NEW_LINE INDENT maxSize = a [ j - 1 ] NEW_LINE totalNumbers = maxSize * lenn NEW_LINE currNumbers = pSum [ j ] - pSum [ i ] NEW_LINE if ( currNumbers + k >= totalNumbers ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT i += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT arr = [ 1 , 1 , 1 ] NEW_LINE k = 7 NEW_LINE print ( maxEqualIdx ( arr , k ) ) NEW_LINE