Queries to find minimum absolute difference between adjacent array elements in given ranges | Javascript program for the above approach ; Stores the index for the minimum value in the subarray arr [ i , j ] ; Structure for query range ; Function to fill the lookup array lookup [ ] [ ] in the bottom up manner ; Initialize M for the intervals with length 1 ; Find the values from smaller to bigger intervals ; Compute minimum value for all intervals with size 2 ^ j ; For arr [ 2 ] [ 10 ] , compare arr [ lookup [ 0 ] [ 3 ] ] and arr [ lookup [ 3 ] [ 3 ] ] ; Otherwise ; Function find minimum of absolute difference of all adjacent element in subarray arr [ L . . R ] ; For [ 2 , 10 ] , j = 3 ; For [ 2 , 10 ] , compare arr [ lookup [ 0 ] [ 3 ] ] and arr [ lookup [ 3 ] [ 3 ] ] , ; Function to find the minimum of the ranges for M queries ; Fills table lookup [ n ] [ Log n ] ; Compute sum of all queries ; Left and right boundaries of current range ; let sum of current query range ; Function to find the minimum absolute difference in a range ; diff [ ] is to stores the absolute difference of adjacent elements ; Call Min_difference to get minimum difference of adjacent elements ; Driver Code
let MAX = 500 ; let lookup = new Array ( MAX ) . fill ( 0 ) . map ( ( ) => new Array ( MAX ) . fill ( 0 ) ) ; class Query { constructor ( l , r ) { this . L = l ; this . R = r ; } } function preprocess ( arr , n ) { for ( let i = 0 ; i < n ; i ++ ) lookup [ i ] [ 0 ] = i ; for ( let j = 1 ; 1 << j <= n ; j ++ ) { for ( let i = 0 ; i + ( 1 << j ) - 1 < n ; i ++ ) { if ( arr [ lookup [ i ] [ j - 1 ] ] < arr [ lookup [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] ] ) lookup [ i ] [ j ] = lookup [ i ] [ j - 1 ] ; else lookup [ i ] [ j ] = lookup [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] ; } } } function query ( arr , L , R ) { let j = Math . floor ( Math . log ( R - L + 1 ) ) ; if ( arr [ lookup [ L ] [ j ] ] <= arr [ lookup [ R - ( 1 << j ) + 1 ] [ j ] ] ) return arr [ lookup [ L ] [ j ] ] ; else return arr [ lookup [ R - ( 1 << j ) + 1 ] [ j ] ] ; } function Min_difference ( arr , n , q , m ) { preprocess ( arr , n ) ; for ( let i = 0 ; i < m ; i ++ ) { let L = q [ i ] . L , R = q [ i ] . R ; document . write ( query ( arr , L , R - 1 ) + " " ) ; } } function minimumDifference ( arr , q , N , m ) { let diff = new Array ( N ) ; for ( let i = 0 ; i < N - 1 ; i ++ ) diff [ i ] = Math . abs ( arr [ i ] - arr [ i + 1 ] ) ; Min_difference ( diff , N - 1 , q , m ) ; } let arr = [ 2 , 6 , 1 , 8 , 3 , 4 ] ; let N = arr . length ; let Q = [ new Query ( 0 , 3 ) , new Query ( 1 , 5 ) , new Query ( 4 , 5 ) ] ; let M = Q . length ; minimumDifference ( arr , Q , N , M ) ;