Minimum number of jumps required to sort numbers placed on a number line | Function to find the minimum number of jumps required to sort the array ; Base Case ; Store the required result ; Stores the current position of elements and their respective maximum jump ; Used to check if a position is already taken by another element ; Stores the sorted array a [ ] ; Traverse the array w [ ] & update positions jumps array a [ ] ; Sort the array a [ ] ; Traverse the array a [ ] over the range [ 1 , N - 1 ] ; Store the index of current element and its just smaller element in array w [ ] ; Iterate until current element position is at most its just smaller element position ; Update the position of the current element ; Print the result ; Driver Code
function minJumps ( w , l , n ) { if ( n == 1 ) { document . write ( 0 ) ; return ; } var ans = 0 ; var i ; var pos = new Map ( ) ; var jump = new Map ( ) ; var filled = new Map ( ) ; var a = new Array ( n ) ; for ( i = 0 ; i < n ; i ++ ) { pos . set ( w [ i ] , i ) ; filled . set ( i , true ) ; jump . set ( w [ i ] , l [ i ] ) ; a [ i ] = w [ i ] ; } a = a . sort ( function ( p , q ) { return p - q ; } ) ; for ( curr = 1 ; curr < n ; curr ++ ) { var currElementPos = pos . get ( a [ curr ] ) ; var prevElementPos = pos . get ( a [ curr - 1 ] ) ; if ( currElementPos > prevElementPos ) continue ; while ( currElementPos <= prevElementPos filled [ currElementPos ] ) { currElementPos += jump . get ( a [ curr ] ) ; ans += 1 ; } pos . set ( a [ curr ] , currElementPos ) ; filled . set ( currElementPos , true ) ; } document . write ( ans ) ; } var W = [ 2 , 1 , 4 , 3 ] ; var L = [ 4 , 1 , 2 , 4 ] ; var N = W . length ; minJumps ( W , L , N ) ;