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 problem is about figuring 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 figure 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 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

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 (sober) perspective.

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 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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