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
def minJumps ( w , l , n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT print ( 0 ) NEW_LINE return NEW_LINE DEDENT ans = 0 NEW_LINE pos = { } NEW_LINE jump = { } NEW_LINE filled = { } NEW_LINE a = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT pos [ w [ i ] ] = i NEW_LINE filled [ i ] = True NEW_LINE jump [ w [ i ] ] = l [ i ] NEW_LINE a [ i ] = w [ i ] NEW_LINE DEDENT a . sort ( ) NEW_LINE for curr in range ( 1 , n , 1 ) : NEW_LINE INDENT currElementPos = pos [ a [ curr ] ] NEW_LINE prevElementPos = pos [ a [ curr - 1 ] ] NEW_LINE if ( currElementPos > prevElementPos ) : NEW_LINE INDENT continue NEW_LINE DEDENT while ( currElementPos <= prevElementPos or ( currElementPos in filled and filled [ currElementPos ] ) ) : NEW_LINE INDENT currElementPos += jump [ a [ curr ] ] NEW_LINE ans += 1 NEW_LINE DEDENT pos [ a [ curr ] ] = currElementPos NEW_LINE filled [ currElementPos ] = True NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT W = [ 2 , 1 , 4 , 3 ] NEW_LINE L = [ 4 , 1 , 2 , 4 ] NEW_LINE N = len ( W ) NEW_LINE minJumps ( W , L , N ) NEW_LINE DEDENT