Find the Sub | Python3 program to find subarray with sum closest to 0 ; Returns subarray with sum closest to 0. ; To consider the case of subarray starting from beginning of the array ; Store prefix sum with index ; Sort on the basis of sum ; Find two consecutive elements with minimum difference ; Update minimum difference and starting and ending indexes ; Return starting and ending indexes ; Driver code
class prefix : NEW_LINE INDENT def __init__ ( self , sum , index ) : NEW_LINE INDENT self . sum = sum NEW_LINE self . index = index NEW_LINE DEDENT DEDENT def findSubArray ( arr , n ) : NEW_LINE INDENT start , end , min_diff = None , None , float ( ' inf ' ) NEW_LINE pre_sum = [ None ] * ( n + 1 ) NEW_LINE pre_sum [ 0 ] = prefix ( 0 , - 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT pre_sum [ i ] = prefix ( pre_sum [ i - 1 ] . sum + arr [ i - 1 ] , i - 1 ) NEW_LINE DEDENT pre_sum . sort ( key = lambda x : x . sum ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT diff = pre_sum [ i ] . sum - pre_sum [ i - 1 ] . sum NEW_LINE if min_diff > diff : NEW_LINE INDENT min_diff = diff NEW_LINE start = pre_sum [ i - 1 ] . index NEW_LINE end = pre_sum [ i ] . index NEW_LINE DEDENT DEDENT return ( start + 1 , end ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 3 , - 4 , - 1 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE point = findSubArray ( arr , n ) NEW_LINE print ( " Subarray ▁ starting ▁ from " , point [ 0 ] , " to " , point [ 1 ] ) NEW_LINE DEDENT