I received an email from HackerRank a few days ago, “Can you solve the ‘Almost sorted’ challenge?”. Well, I thought, probably.. let me see.
The “Almost sorted” challenge
Figure out how to complete the sorting of an array of integers, we receive an input like the following:
1, 2, 8, 4, 5, 6, 7, 3, 9
The goal is to find out how the input array can be transformed into a sorted array, using only one of two allowed operations:
- Swap two elements
- Reverse a continuous subsequence of the array
The text of the challenge requires to print out the operation that can complete the sorting. If two elements can be swapped then we have to print
swap l r where
r are the positions of the two items to be swapped. If, on the other hand, a subsequence can be reversed to complete the sorting, then we print
reverse s e where
e are the initial and final positions of the subsequence. When printing the positions we have to use 1 based numbers.
Using the array above we should therefore be able to print
swap 3 8
The first approach
At this point I should say that the email came on a Friday evening, and for some reason I am usually not in my best programming mood on a Friday evening, especially in Amsterdam. However I tried to think through how to do this while drinking my (~third) beer, it didn’t work out. So I tried again the day after and I solved it in 10 minutes, because the solution is actually pretty straightforward, once you look at the problem from the right perspective.
The approach that worked
If you struggle with this challenge I suggest you go check the quick sort algorithm again, because the idea here is kind of similar. What we have to do is start looking at the array from both ends, just keep two pointers
r, then keep moving
r towards the center of the array until an element is found which should be moved in order to sort the array. We have to find two such elements, otherwise the array is either already sorted or cannot be sorted using the allowed operations, consider this array:
1, 2, 3, 12, 5, 6, 7, 8, 9
In this case
r will end up both at element
12 There are no items which can be swapped in order to sort the array, reversing is also not an option.
If on the other hand, we can find two distinct elements which can be swapped, then we have the first hint that we can potentially sort the array using one of the two allowed operations. What we could do at this point is swapping the two items, check if the array is sorted, and we would have solved the first part of the challenge, detecting
But how about
reverse is just
swap done more than once. We can detect
reverse by keeping advancing the
r pointers towards each other, swap the items if needed, that is to say, only if they need to be swapped, and count how many swaps we did. If the number of swaps is equal to half of the total elements that we walked through then we can sort the array using
reverse. If the number of swaps is one, then we can sort the array using
So that’s the basic idea, find the Python 3 implementation below, I hope this post helped those of you who got stuck at this, as you can see it’s easier than it seems 🙂
Looking for an awesome book on algorithms? Have a look at Algorithms (4th Edition), it’s a great book, it covers a lot of topics from sorting to graphs to strings processing algorithms and can teach you a lot on the subject!