Arrays: Get minimum number of moves to sort an array

Problem Statement:

You are given an array and elements are in the range of 1 to n.

You need to count the number of move to front operations to make the array sorted.

move-to-front means, picking any item and place it in first position.

Example:

Input: arr[] = {3, 2, 1, 4}.

Output : 2

Step 1: Take 2 and place it on the top. The array becomes {2, 3, 1, 4}

Step 2: Take 1 and place it on the top. The array becomes {1, 2, 3, 4}

So the output is 2.

Solution Explanation:

Solution is very simple.

Traverse the array from the end.

We take a variable “minSteps” and initialize with length of the array.

Now start from the last element of the array, and if the current element is same as the “minSteps”, then decrease the “minSteps” by 1.

At the end return the “minSteps” value

Time Complexity : O(n)

Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>

using namespace std;

int solution(int arr[], int n) 
{ 

	int minSteps = n; 

	for (int i=n-1; i >= 0; i--) 
	{ 
		if (arr[i] == minSteps) 
			minSteps--; 
	} 

	return minSteps; 
} 

int main() 
{ 
	int arr[] = {3, 2, 1, 4}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	cout << solution(arr, n); 
	return 0; 
} 

Output

2