Find minimum length sub | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX_INT  1000000 NEW_LINE int solve ( int Array [ ] , int N ) { vector < int > pos [ 5 ] ; int pref [ 5 ] = { 0 } ; if ( Array [ 0 ] == 0 ) { pref [ 0 ] = 1 ; pos [ 0 ] . push_back ( 0 ) ; } int ans = MAX_INT ; for ( int i = 1 ; i < N ; i ++ ) { if ( Array [ i ] == 0 ) { pref [ 0 ] ++ ; pos [ 0 ] . push_back ( i ) ; } else { if ( pref [ Array [ i ] - 1 ] > 0 ) { pref [ Array [ i ] ] ++ ; pos [ Array [ i ] ] . push_back ( i ) ; if ( Array [ i ] == 4 ) { int end = i ; int start = i ; for ( int j = 3 ; j >= 0 ; j -- ) { int s = 0 ; int e = pos [ j ] . size ( ) - 1 ; int temp = -1 ; while ( s <= e ) { int m = ( s + e ) / 2 ; if ( pos [ j ] [ m ] <= start ) { temp = pos [ j ] [ m ] ; s = m + 1 ; } else { e = m - 1 ; } } start = temp ; } ans = min ( ans , end - start + 1 ) ; } } } } return ans ; } int main ( ) { int Array [ ] = { 0 , 1 , 2 , 3 , 4 , 2 , 0 , 3 , 4 } ; int N = sizeof ( Array ) / sizeof ( Array [ 0 ] ) ; cout << solve ( Array , N ) ; return 0 ; }