### Glydon's blog

By Glydon, history, 7 months ago,

As I didn't get the solution provided in the editorial of 1585D - Yet Another Sorting Problem and how it can be done with O(N)

I had come up with this logic O(NlogN):

1st-> If there is a duplicate element, we can sort the whole array with the help of those two using the 3-cycle technique so always "YES"

2nd-> if there is no duplicate present, simply take one element at a time and place that element into its perfect position (the position where it should be if it was sorted) using the 3 cycles technique.
When 2 elements are remaining and they are not sorted it means they can't be sorted as you require 3 elements to sort!

There might be better solutions available but I guess it's easy to understand and observe also.

• +10

 » 7 months ago, # |   +3 Can you please explain why we can always sort using duplicates?
•  » » 7 months ago, # ^ |   +3 As you have at least 1 duplicate value , lets say X as count of X >= 2 (we will consider count of X = 2 here ) so if ith index need some value Y and Y!=X , find Y's position in arr , lets say its j So put one X in position i using 3 cycle technique and let the 2nd X's position is kso now simply do 3 cycle sort on these 3 like -- temp = a[i] a[i] = a[j] a[j] = a[k] a[k] = temp keep repeating this index by index ; at the end, you might see the array is sorted OR 2 elements are misplaced one of which will be X and you know what you have to perform! just perform 3 cycle sort using X, X, left_value_to_be_sorted this is only leading us to the correct solution as X has 2 different positions that is considered to be its position. Flexibility is the key here.My explanation is a mess! Please grab a pen and paper, you will understand better, sorry I have confused you.
 » 7 months ago, # |   0 From your blog it's not clear why either of these statements are true. Care to explain?
•  » » 7 months ago, # ^ |   0 I have explained above about 2 duplicates, In short as per observation you can always see when you have no duplicates You can reach a sorted situation in max (n-2) steps, because when (n-2) elements can always be arranged in the right order and always 2 elements are left to judge if those 2 are in the correct order or not, if those remaining two values are not in the correct order then they cant be sorted otherwise it's sorted.I can't prove mathematically, sorry for the inconvenience , and if this post is really that misleading I will have to remove it. Either way, I will like it if Some1 proves this wrong. I am just Newbie. I will not be Upset even if I am proven wrong. I thought of sharing this in the first place because it got accepted :(
 » 7 months ago, # |   +6 anotherTry -is-this-fft- Let me try to explain the trick about duplicates. The thing is, we can swap any pair $i$ and $j$ in the array with each other if we have at least one pair of duplicates. Let the $d_{1}$ and $d_{2}$ be the numbers which are same. If we want to swap $i$ and $j$, then: First 3-cycle $(i,j,d_{1})$ then $(j,d_{1},d_{2})$. Visualization: $\quad i \quad j \quad d_{1} \quad d_{2}$ (the order of these doesn't matter) $\quad d_{1} \quad i \quad j \quad d_{2} \newline \quad j \quad i \quad d_{2} \quad d_{1}$ As you see, $d_{1}$ and $d_{2}$ change as well but since they are same it doesn't matter. If we want to change $d_{1}$ and any other number $i$, than 3-cycle $(i,d_{1},d_{2})$ will do it. $\quad i \quad d_{1} \quad d_{2} \newline \quad d_{2} \quad i \quad d_{1}$ (again $d_{1}$ and $d_{2}$ same, so it's done) As a result, we can do a regular swap operation to any pair. Hence the answer is always yes.
 » 7 months ago, # |   0 By the way, this solution is $O(n)$ as well. Why did you said $O(n*log(n))$?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +2 I needed a duplicate sorted array to compare if the particular element is in its correct position or not, that's why. Give Downvote if you hated
•  » » » 7 months ago, # ^ |   0 It says $1 \le a_{i} \le n$ in the problem statement. Therefore, when all elements are different, they are the permutation of the numbers $1$ to $n$. So, value of a number equal to the correct position of that number. By the way, I had upvoted your post before I comment. I just tried to say this solution can be done in $O(n)$ as well.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +11 I just saw your submission of D, and realized I missed a constraint that 1 <= Ai <= n , I solved for in general! Independent of that Constraint :p If you consider that constraint then its O(N) solution
 » 7 months ago, # |   0 Hey, your solution is really good. Took me some time to figure out how it is working but WOW.
•  » » 7 months ago, # ^ |   +11 glad you liked it :)