Minimum number of jumps required to sort numbers placed on a number line | Java program for the above approach ; 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
import java . util . * ; class GFG { static void minJumps ( int [ ] w , int [ ] l , int n ) { if ( n == 1 ) { System . out . print ( 0 ) ; return ; } int ans = 0 ; HashMap < Integer , Integer > pos = new HashMap < Integer , Integer > ( ) ; HashMap < Integer , Integer > jump = new HashMap < Integer , Integer > ( ) ; HashMap < Integer , Boolean > filled = new HashMap < Integer , Boolean > ( ) ; int [ ] a = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { if ( pos . containsKey ( w [ i ] ) ) pos . put ( w [ i ] , i ) ; else pos . put ( w [ i ] , i ) ; if ( filled . containsKey ( w [ i ] ) ) filled . put ( i , true ) ; else filled . put ( i , true ) ; if ( jump . containsKey ( w [ i ] ) ) jump . put ( w [ i ] , l [ i ] ) ; else jump . put ( w [ i ] , l [ i ] ) ; a [ i ] = w [ i ] ; } Arrays . sort ( a ) ; for ( int curr = 1 ; curr < n ; curr ++ ) { int currElementPos = pos . get ( a [ curr ] ) ; int prevElementPos = pos . get ( a [ curr - 1 ] ) ; if ( currElementPos > prevElementPos ) continue ; while ( currElementPos <= prevElementPos || filled . containsKey ( currElementPos ) && filled . containsKey ( currElementPos ) ) { currElementPos += jump . get ( a [ curr ] ) ; ans ++ ; } if ( pos . containsKey ( a [ curr ] ) ) pos . put ( a [ curr ] , currElementPos ) ; else pos . put ( a [ curr ] , currElementPos ) ; if ( filled . containsKey ( currElementPos ) ) filled . put ( currElementPos , true ) ; else filled . put ( currElementPos , true ) ; } System . out . print ( ans ) ; } public static void main ( String [ ] args ) { int [ ] W = { 2 , 1 , 4 , 3 } ; int [ ] L = { 4 , 1 , 2 , 4 } ; int N = W . length ; minJumps ( W , L , N ) ; } }