Count minimum number of "move-to-front" moves to sort an array - GeeksforGeeks
Given an array of size n such that array elements are in range from 1 to n. The task is to count number of move-to-front operations to arrange items as {1, 2, 3,… n}. The move-to-front operation is to pick any item and place it at first position.
Read full article from Count minimum number of "move-to-front" moves to sort an array - GeeksforGeeks
Given an array of size n such that array elements are in range from 1 to n. The task is to count number of move-to-front operations to arrange items as {1, 2, 3,… n}. The move-to-front operation is to pick any item and place it at first position.
The idea is to traverse array from end. We expect n at the end, so we initialize expectedItem as n. All the items which are between actual position of expectedItem and current position must be moved to front. So we calculate the number of items between current item and expected item. Once we find expectedItem, we look for next expectedItem by reducing expectedITem by one.
int minMoves(int arr[], int n){ // Since we traverse array from end, extected item // is initially n int expectedItem = n; // Taverse array from end for (int i=n-1; i >= 0; i--) { // If current item is at its correct position, // decrement the expectedItem (which also means // decrement in minimum number of moves) if (arr[i] == expectedItem) expectedItem--; } return expectedItem;}