HackerRank “Almost Sorted” challenge

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:

  1. Swap two elements
  2. 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 l and 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 s an 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 l and r, then keep moving l and 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 l and 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 swap operations.

But how about reverse? Well, reverse is just swap done more than once. We can detect reverse by keeping advancing the l and 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 swap.

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!

Unique opportunity! Help a fellow grow his blog!

Hi there! If you’ve read this far maybe you think this was useful, or fun, or I don’t know what but for some reason You Got Here! Great! Please consider sharing this post with your network, I am trying to get The Code Butchery to grow so I can provide more content like this, will you help me in my journey? Thank you!

Share this

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.