Problem Link :- B. Minimize the Permutation
My Code :- My Code
Ive been struggling for 3 hours straight and I’m still not able to find the solution to and get an AC in the problem . You can get the question above .
Approach :
Just Applying the brute force , getting the smallest number , and putting in the leftmost position possible . and while putting it making sure that , the i -th operation is never performed while maintaining a check array .
I’m Not able to get the answer , somebody Please help .
Hint : An array having 1st element as 1 is always smaller than any other array. Think on similar lines.
Editorial
I think the problem is where you are checking num+1!=i. When num+1==i it isn’t guaranteed that all smaller numbers than i are to the left, and also in sorted manner. So, irrespective of if num+1 is i or not, you should move it to the left if you can.
Yes exactly I agree with you , I’m moving the smallest number to its optimal position which is when index+1 == i
if we are able to achieve this , then we do this and if not , we move to the next number .
But since we are taking the smallest number first , then we are sure that , the previous smaller numbers than i are either in their correct position or they are not able to move , because some operations already happened ( which we are checking using check array ) .
For eg 15 3 4 2
then to process 3
, before that 2
is processed , and since we are moving from smallest to biggest number therefore , the next number after 2
will either be on its leftmost position i.e. num+1==i
or it will be not , therefore we will proceed only when num+1!=i
, and if we proceed when num+1==i
but we want the string to be lexo , the optimal place for number i
should be its num+1==i
.
so i think we can’t move left further than this .