Smallest Subarray with Sum K from an Array | Python3 program to implement the above approach ; Function to find the length of the smallest subarray with sum K ; Stores the frequency of prefix sums in the array ; Initialize ln ; If sum of array till i - th index is less than K ; No possible subarray exists till i - th index ; Find the exceeded value ; If exceeded value is zero ; Driver Code
from collections import defaultdict NEW_LINE import sys NEW_LINE def subArraylen ( arr , n , K ) : NEW_LINE INDENT mp = defaultdict ( lambda : 0 ) NEW_LINE mp [ arr [ 0 ] ] = 0 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT arr [ i ] = arr [ i ] + arr [ i - 1 ] NEW_LINE mp [ arr [ i ] ] = i NEW_LINE DEDENT ln = sys . maxsize NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] < K ) : NEW_LINE INDENT continue NEW_LINE DEDENT else : NEW_LINE INDENT x = K - arr [ i ] NEW_LINE if ( x == 0 ) : NEW_LINE INDENT ln = min ( ln , i ) NEW_LINE DEDENT if ( x in mp . keys ( ) ) : NEW_LINE INDENT continue NEW_LINE DEDENT else : NEW_LINE INDENT ln = min ( ln , i - mp [ x ] ) NEW_LINE DEDENT DEDENT DEDENT return ln NEW_LINE DEDENT arr = [ 1 , 2 , 4 , 3 , 2 , 4 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE K = 7 NEW_LINE ln = subArraylen ( arr , n , K ) NEW_LINE if ( ln == sys . maxsize ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ln ) NEW_LINE DEDENT