PROBLEM LINK:
Author: Prakhar Gupta
Tester: Madhav Sainanee
Editorialist: Prakhar Gupta
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
Given an array A of N distinct elements, we can move any element to the end. Find the minimum number of moves to sort the array in ascending order.
QUICK EXPLANATION
Suppose B be the sorted version of A. Let cnt be the longest subsequence of A which is a prefix of B. The minimum number of moves are N - cnt.
EXPLANATION:
Let the original array be A and its sorted version be B.
We call two elements ordered if A_i < A_j and i < j. If they are unordered, the only way to make them ordered is to put A_i to the end, as it is the only move we are allowed.
For a sorted array, all consecutive pairs of elements are ordered.
So, we start from i = 0 in B and look at the pair of elements B_i and B_{i+1} in A. If they are not ordered, it means that B_{i+1} is coming before B_i in A. So, we have to send B_{i+1} to the end of A. This makes B_{i+1} unordered with B_{i+2}, B_{i+3} and so on.
So essentially, we exclude the elements which are already ordered from the start of B and move the others to the end.
This ultimately comes down to finding the largest prefix of B that is a subsequence of A.
This can be achieved by a map/dictionary, or an array of pairs containing the index of the element in the original array and sorting it.
Complexity: The time complexity is O(N log(N)) per test case, due to sorting.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.