PROBLEM LINK:
BALASEQ - Morty And His Two Sequences
Author: ashu181998
Editorialist: Ashutosh Sundriyal
DIFFICULTY: EASY-MEDIUM
PROBLEM:
Given two sequences of length N, each containing same non-repeating integers. You need to convert the first sequence into second. In one move one can either remove the first or the last element from the first sequence and insert it in any position in the same squence itself. We have to calculate the minimum number of such moves ( possibly zero ) to convert the first sequence into second.
EXPLANATION:
The thing to observe here is that if we replace each number in the first sequence with position of that number in the second sequence, the problem reduces to sorting the first sequence.
Another observation is that the longest increasing subarray in this new array formed remains uneffected as these are the elements which are in the correct order they need to be in and the rest elements end up adjusting around these elements. And now the reduced problem is calculating the length of the longest increasing subarray and the final output is N - (length of the longest inc. subarray).
So, this solution runs in O(n).
SOLUTION:
Editorialist’s solution can be found here.