Find minimum length sub | Python3 implementation of the approach ; Function to return the minimum length of a sub - array which contains 0 , 1 , 2 , 3 , 4 as a sub - sequence ; To store the indices where 0 , 1 , 2 , 3 and 4 are present ; To store if there exist a valid prefix of sequence in array ; Base Case ; If current element is 0 ; Update the count of 0 s till now ; Push the index of the new 0 ; To check if previous element of the given sequence is found till now ; If it is the end of sequence ; Iterate for other elements of the sequence ; Binary Search to find closest occurrence less than equal to starting point ; Update the starting point ; Driver code
MAX_INT = 1000000 NEW_LINE def solve ( Array , N ) : NEW_LINE INDENT pos = [ [ ] for i in range ( 5 ) ] NEW_LINE pref = [ 0 for i in range ( 5 ) ] NEW_LINE if ( Array [ 0 ] == 0 ) : NEW_LINE INDENT pref [ 0 ] = 1 NEW_LINE pos [ 0 ] . append ( 0 ) NEW_LINE DEDENT ans = MAX_INT NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( Array [ i ] == 0 ) : NEW_LINE INDENT pref [ 0 ] += 1 NEW_LINE pos [ 0 ] . append ( i ) NEW_LINE DEDENT else : NEW_LINE INDENT if ( pref [ Array [ i ] - 1 ] > 0 ) : NEW_LINE INDENT pref [ Array [ i ] ] += 1 NEW_LINE pos [ Array [ i ] ] . append ( i ) NEW_LINE if ( Array [ i ] == 4 ) : NEW_LINE INDENT end = i NEW_LINE start = i NEW_LINE for j in range ( 3 , - 1 , - 1 ) : NEW_LINE INDENT s = 0 NEW_LINE e = len ( pos [ j ] ) - 1 NEW_LINE temp = - 1 NEW_LINE while ( s <= e ) : NEW_LINE INDENT m = ( s + e ) // 2 NEW_LINE if ( pos [ j ] [ m ] <= start ) : NEW_LINE INDENT temp = pos [ j ] [ m ] NEW_LINE s = m + 1 NEW_LINE DEDENT else : NEW_LINE INDENT e = m - 1 NEW_LINE DEDENT DEDENT start = temp NEW_LINE DEDENT ans = min ( ans , end - start + 1 ) NEW_LINE DEDENT DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT Array = [ 0 , 1 , 2 , 3 , 4 , 2 , 0 , 3 , 4 ] NEW_LINE N = len ( Array ) NEW_LINE print ( solve ( Array , N ) ) NEW_LINE