Find minimum length sub | Javascript 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
let MAX_INT = 1000000 ; function solve ( array , N ) { let pos = new Array ( 5 ) ; for ( let i = 0 ; i < 5 ; i ++ ) { pos [ i ] = new Array ( 10000 ) ; for ( let j = 0 ; j < 10000 ; j ++ ) { pos [ i ] [ j ] = 0 ; } } let pref = new Array ( 5 ) ; for ( let i = 0 ; i < 5 ; i ++ ) { pref [ i ] = 0 ; } if ( array [ 0 ] == 0 ) { pref [ 0 ] = 1 ; pos [ 0 ] [ pos [ 0 ] . length - 1 ] = 0 ; } let ans = MAX_INT ; for ( let i = 1 ; i < N ; i ++ ) { if ( array [ i ] == 0 ) { pref [ 0 ] ++ ; pos [ 0 ] [ pos [ 0 ] . length - 1 ] = i ; } else { if ( pref [ array [ i ] - 1 ] > 0 ) { pref [ array [ i ] ] ++ ; pos [ array [ i ] ] [ pos [ array [ i ] ] . length - 1 ] = i ; if ( array [ i ] == 4 ) { let end = i ; let start = i ; for ( let j = 3 ; j >= 0 ; j -- ) { let s = 0 ; let e = pos [ j ] . length - 1 ; let temp = - 1 ; while ( s <= e ) { let m = Math . floor ( ( s + e ) / 2 ) ; if ( pos [ j ] [ m ] <= start ) { temp = pos [ j ] [ m ] ; s = m + 1 ; } else e = m - 1 ; } start = temp ; } ans = Math . min ( ans , end - start + 1 ) ; } } } } return ans ; } let array = [ 0 , 1 , 2 , 3 , 4 , 2 , 0 , 3 , 4 ] ; let N = array . length ; document . write ( solve ( array , N ) ) ;