Smallest index in given range of indices which is not equal to X | Precompute the index of next different element in the array for every array element ; Default value ; Compute nextpos [ i ] using nextpos [ i + 1 ] ; Function to return the smallest index ; nextpos [ i ] will store the next position p where arr [ p ] != arr [ i ] ; If X is not present at l ; Otherwise ; Find the index which stores a value different from X ; If that index is within the range ; Driver Code
function precompute ( nextpos , arr , N ) { nextpos [ N - 1 ] = N ; for ( var i = N - 2 ; i >= 0 ; i -- ) { if ( arr [ i ] == arr [ i + 1 ] ) nextpos [ i ] = nextpos [ i + 1 ] ; else nextpos [ i ] = i + 1 ; } } function findIndex ( query , arr , N , Q ) { var nextpos = Array ( N ) ; precompute ( nextpos , arr , N ) ; for ( var i = 0 ; i < Q ; i ++ ) { var l , r , x ; l = query [ i ] [ 0 ] ; r = query [ i ] [ 1 ] ; x = query [ i ] [ 2 ] ; var ans = - 1 ; if ( arr [ l ] != x ) ans = l ; else { var d = nextpos [ l ] ; if ( d <= r ) ans = d ; } document . write ( ans + " " ) ; } } var N , Q ; N = 6 ; Q = 3 ; var arr = [ 1 , 2 , 1 , 1 , 3 , 5 ] ; var query = [ [ 0 , 3 , 1 ] , [ 1 , 5 , 2 ] , [ 2 , 3 , 1 ] ] ; findIndex ( query , arr , N , Q ) ;