Almost Sorted Hacker Rank Problem (Medium Difficulty)

Recently I came across this problem in hacker rank. This problem is really fascinating as it teaches you to handle a lot of edge cases and variables at the same time. So, I thought of writing an article on this one. I hope you will enjoy it as much as I enjoyed solving it.

Simplified Problem Statement

You will be given an array of N integers. This array could be completely sorted or almost sorted as the problem states.

If the array is sorted then it is fantastic you don’t have to do anything but if the array is not sorted then you are left with 2 options –

• Perform a swap operation
• Perform a reverse operation

But you can only perform any one of the above operations and you can perform them once. And once you have performed the operation the final array should be sorted.

The output of the program should be in one of the below formats:

yes
swap {index1} {index2}

Or,

yes
reverse {index1} {index2}

Or,

no

The problem seems complicated just by reading it. But if you spend some time with the problem you start to see a pattern.

Easy Approach

The problematic area in the above problem is to identify the points from where the order changes from ascending to descending and then from descending to ascending.

Sorted array approach is the easiest one when it comes to identifying these ups and downs in the array.

Step 1 – Find Points Where Order Changes

The easiest approach is to sort the given array.

As you can see in the image below.

I’ve sorted the array and then compared their indices. And whenever there was a mismatch in the value I recorded the start and end position. Along with the start and end position, I also counted the number of mismatches.

This count variable will later help us to differentiate between SWAP and REVERSE operation.

The code to fetch the above information is as follows:

vector<int> sorted_arr = arr;
sort(sorted_arr.begin(), sorted_arr.end());

int start = -1, end = -1, count = 0, len = sorted_arr.size();

for (int i=0; i < len; i++) {
    if (sorted_arr[i] != arr[i]) {
        if  (start == -1) start = i;
        else end = i;

        count++;
    }
}    

Once you have the above information regarding the start pointer, end pointer and count, you can write the code to identify which operations to perform to sort the array.

Let’s start with the first case.

Case 1 – SWAP Two Numbers

This case is straightforward once you have the count information with you.

All you have to check is that the count==2.

If the count is 2 it means that there are only two places where the array values mismatched. This means that there is a probability that if we swap these two values, we might get the sorted array.

But mind you there are a lot of edge cases in the above scenario. You will have to cover all the edge cases otherwise your program will break.

The code for the above check is as followed:

    if (count == 2) {
        // next to each other
        if ((start == 0  && end - start == 1) || 
            (end == len - 1 && end - start == 1) || 
            (start > 0 && end == len - 1 && arr[end] > arr[start - 1]) ||
            (arr[start] < arr[end + 1] && arr[end] > arr[start - 1])) {
            return "yes\nswap " + to_string(start + 1) + " " + to_string(end + 1);
        } 

        return "no";
    }

The conditions do look complex but they are actually there to take care of the edge conditions.

The edges conditions are mostly the start and end indices of the array.

In the simplest condition to check and see if the swap operation will sort the array is to check the following:

arr[start] < arr[end - 1] AND arr[end] > arr[start - 1]

If the above condition is satisfied then swap operation can be performed successfully. The rest is just to take care of the edge cases.

Case 2 – REVERSE Sub-Array

The reverse operation is a little bit more complex as it involves one extra step to test that the subarray (5..2) is actually a sorted array in the descending order. Take a look at the below example:

This check is simple. And if the sub-array is not stored then it means that the array cannot be sorted by a reverse operation. So, we will return “no” and we are done.

for (int i = start; i < end; i++) 
        if (arr[i] < arr[i+1]) return "no";

But if the sub-array is in descending order then we will have to perform certain checks to make sure that the reverse operation will sort the array.

Again, there are edge cases because of which the conditions start to look daunting but it really isn’t. The thing that we are checking is this:

arr[end] > arr[start - 1] AND arr[start] < arr[end  + 1]

This means that (from the above array) 2 should always be bigger than 1. And 5 should always be smaller than 6. If this condition is satisfied then the reversing the subarray will definitely result in a sorted array.

The code for the same is as follows:

    if ((start == 0 && end == len - 1)                                  || 
            ((start == 0 && end + 1 < len) && arr[start] < arr[end + 1])    || 
            ((end == len - 1 && arr[end] > arr[start - 1]))                 || 
            (arr[end] > arr[start - 1] && arr[start] < arr[end  + 1]))
                return "yes\nreverse " + to_string(start + 1) + " " + to_string(end + 1);
        
        return "no";

Final Code

So, the final pieces of the code are –

• Sort the array
• Find the indices where the values are different
• Keep track of the first mismatch and the last mismatch.
• Keep track of the number of mismatches.
• Solve for SWAP case
• Solve for the REVERSE case

Time Complexity – O(nlogn)

There is an O(n) solution available but I will leave that for you to implement.

When we merge our code together this is what we get:

string almost_sorted_nlogn(vector<int> &arr) {
    vector<int> sorted_arr = arr;
    sort(sorted_arr.begin(), sorted_arr.end());

    int start = -1, end = -1, count = 0, len = sorted_arr.size();

    for (int i=0; i < len; i++) {
        if (sorted_arr[i] != arr[i]) {
            if  (start == -1) start = i;
            else end = i;

            count++;
        }
    }

    if (count == 2) {
        // next to each other
        if ((start == 0  && end - start == 1) || 
            (end == len - 1 && end - start == 1) || 
            (start > 0 && end == len - 1 && arr[end] > arr[start - 1]) ||
            (arr[start] < arr[end + 1] && arr[end] > arr[start - 1])) {
            return "yes\nswap " + to_string(start + 1) + " " + to_string(end + 1);
        } 

        return "no";
    }

    if (count > 2) {
        // to check if the segment is in decreasing order
        for (int i = start; i < end; i++) 
            if (arr[i] < arr[i+1]) return "no";
        
        if ((start == 0 && end == len - 1)                                  || 
            ((start == 0 && end + 1 < len) && arr[start] < arr[end + 1])    || 
            ((end == len - 1 && arr[end] > arr[start - 1]))                 || 
            (arr[end] > arr[start - 1] && arr[start] < arr[end  + 1]))
                return "yes\nreverse " + to_string(start + 1) + " " + to_string(end + 1);
        
        return "no";
    }

    return "no";
}

The code is really simple and easy to implement. The only tough thing about this problem was to come up with a solution to find the places where the mismatch of the values starts and ends.

After that, you just have to take care of the edge cases and the code works.

Here’s my submission on Hackerrank – passed all test cases.2020-11-25

Do comment below if you are stuck somewhere or just want to start a discussion around another approach.