# Why the O(n) method is straightforward, could anybody tell me? Thank you!

• Why the O(n) method is straightforward, could anybody tell me? Thank you!

• I havent coded it but this is what I think:
In order traversal the tree, put tree node in a list. Then swap the one bigger than its successor and the one smaller than its predecessor

• Thanks, but I have a problem. For example 1 2 3 4 5 -> 1 4 3 2 5. The 2 and the 4 are swapped. However, 4, 5 are bigger than their predecessor, and 1, 2 are smaller than their successor. How do I know which two should be swapped.

• In a sorted array of distinct elements:
A B C D E F G
If we swap B and F then we have:
A F C D E B G
We can see that the array is in ascending order until F and C, we record this and continue from C.
then at E and B we see the order if wrong again.
So we need to swap F (it is bigger so it comes from a later position) and B (it is smaller so it comes from a earlier position).

There is a special case when we swap two neighbouring elements:
ACBDEFG

where we will only detect the broken order once.

• Thank you so much! Now, I understand it!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.