Minimum operations to sort Array by moving all occurrences of an element to start or end

Given an array arr[] of size N where arr[i] ≤ N, the task is to find the minimum number of operations to sort the array in increasing order where In one operation you can select an integer X and:

• Move all the occurrences of X to the start or
• Move all the occurrences of X to the end.

Examples:

Input: arr[] = {2, 1, 1, 2, 3, 1, 4, 3}, N = 8
Output: 2
Explanation:
First operation -> Select X = 1 and add all the 1 in front. 
The updated array arr[] = {1, 1, 1, 2, 2, 3, 4, 3}.
Second operation -> Select X= 4 and add all the 4 in end.
The updated array arr[ ]  = [1, 1, 1, 2, 2, 3, 3, 4]. 
Hence the array become sorted in two operations.

Input: arr[] = {1, 1, 2, 2}, N = 4
Output: 0
Explanation: The array is already sorted. Hence the answer is 0.

Approach: This problem can be solved using the greedy approach based on the following idea.

The idea to solve this problem is to find the longest subsequence of elements (considering all occurrences of an element) which will be in consecutive positions in sorted form. Then those elements need not to be moved anywhere else, and only moving the other elements will sort array in minimum steps.

Follow the illustration below for a better understanding:

Illustration:

For example arr[] = {2, 1, 1, 2, 3, 1, 4, 3}.

When the elements are sorted they will be {1, 1, 1, 2, 2, 3, 3, 4}. 
The longest subsequence in arr[] which are in consecutive positions as they will be in sorted array is {2, 2, 3, 3}.

So the remaining unique elements are {1, 4} only.
Minimum required operations are 2.

First operation:
        => Move all the 1s to the front of array.
        => The updated array arr[] = {1, 1, 1, 2, 2, 3, 4, 3}

Second operation:
        =>  Move 4 to the end of the array.
        => The updated array arr[] = {1, 1, 1, 2, 2, 3, 3, 4}

Follow the steps below to solve this problem based on the above idea:

• Divide the elements into three categories.
  • The elements that we will move in front.
  • The elements that we will not move anywhere.
  • The elements that we will move in the end.
• So to make the array sorted, these three conditions must satisfy.
  • All the elements of the first category must be smaller than the smallest element of the second category.
  • All the elements in the third category must be larger than the largest element of the second category.
  • If we remove all the elements of the first and third categories, the remaining array must be sorted in non-decreasing order.
• So to minimize the total steps the elements in the second category must be maximum as seen from the above idea.
• Store the first and last occurrence of each element.
• Start iterating from i = N to 1 (consider i as an array element  and not as an index):
  • If its ending point is smaller than the starting index of the element just greater than it then increase the size of the subsequence.
  • If it is not then set it as the last and continue for the other elements.
• The unique elements other than the ones in the longest subsequence is the required answer.

Below is the implementation of the above approach :

2

Time Complexity: O(N)
Auxiliary Space: O(N)

Efficient approach : Space optimization approach

In this approach we can improve the space complexity of the algorithm by using two variables to keep track of the minimum and maximum positions of the given element in the array instead of using a 2D vector O. This will reduce the space complexity from O(N) to O(1).  

Implementation steps : 

• Declare function minOpsSortArray that takes a reference to a vector of integers arr and an integer N as arguments and returns an integer. 
• Take variables minPos, maxPos, and ctr and Initialize variables to N+1, -1, and 0, respectively. 
• Also take variables ans, tot, and last and Initialize variables to 0, 0, and N+1 respectively. 
• Return the difference between ctr and ans.

Implementation : 

2

Time Complexity: O(N)
Auxiliary Space: O(1)