Need help to solve the hackerrank challenge

Question

I'm trying to solve an "Almost Sorted" challenge in hackerrank the problem is:

Given an array with elements, can you sort this array in ascending order using only one of the following operations?

Swap two elements. Reverse one sub-segment.

Input Format The first line contains a single integer, , which indicates the size of the array.

The next line contains integers separated by spaces.

Sample Input #1

2
4 2

Sample Output #1

yes
swap 1 2

Sample Input #2

3

3 1 2

Sample Output #2

no

Sample Input #3

6

1 5 4 3 2 6

Sample Output #3

yes

reverse 2 5

I tried to solve the challenge and my code is working but it seems it's to slow for big arrays.

Kindly asking you to help me to find a better solution for mentioned problem.

Below is my code:

import java.util.*;

public class Solution
{
    private static int[] arr;

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();

        arr = new int[N];

        for (int i = 0; i < N; i++)
        {
            arr[i] = in.nextInt();
        }

        if (IsSorted(arr))
        {
            System.out.println("yes");
            return;
        }

        if(CheckSingleSwap(arr))
            return;

        if(CheckSingleReverse(arr))
            return;

        System.out.println("no");
    }

    private static boolean CheckSingleReverse(int[] arr)
    {
        int length = arr.length;
        int limit = length - 2;
        int current = 1;

        List<Integer> indexes = new ArrayList<Integer>();

        while (current < limit)
        {
            for (int i = 0; i < length; i++)
            {
                int temp = current + i;
                for (int j = i; j <= temp && temp < length; j++)
                {
                    indexes.add(j);
                }

                if (IsSorted(ReverseArrayPart(arr, indexes)))
                {
                    System.out.println("yes");
                    System.out.println("reverse " + (indexes.get(0) + 1) + " " + (indexes.get(indexes.size() - 1) + 1));

                    return true;
                }
                indexes.clear();
            }

            current++;
        }

        return false;
    }

    private static int[] ReverseArrayPart(int[] arr, List<Integer> indexes)
    {
        int[] result = new int[arr.length];
        int[] arrayPart = new int[indexes.size()];
        int j = 0;

        for (int i = 0; i < arr.length; i++)
        {
                if (indexes.contains(i))
                {
                    arrayPart[j] = arr[i];
                    j++;
                }

            result[i] = arr[i];
        }

        for(int i = 0; i < arrayPart.length / 2; i++)
        {
            int temp = arrayPart[i];
            arrayPart[i] = arrayPart[arrayPart.length - i - 1];
            arrayPart[arrayPart.length - i - 1] = temp;
        }

        j = 0;
        for (int i = 0; i < result.length; i++)
        {
                if (indexes.contains(i))
                {
                    result[i] = arrayPart[j];
                    j++;
                }
        }

        return result;
    }

    private static boolean CheckSingleSwap(int[] arr)
    {
        int count = 0;
        int[] B = Arrays.copyOf(arr, arr.length);
        Arrays.sort(B);
        List<Integer> indexes = new ArrayList<Integer>();

        for(int i = 0; i < arr.length; i++)
        {
            if(arr[i] != B[i])
            {
                count++;
                indexes.add(i+1);
            }
        }

        if(count > 2)
            return false;

        System.out.println("yes");
        System.out.println("swap " + indexes.get(0) + " " + indexes.get(1));

        return true;
    }

    private static boolean IsSorted(int[] arr)
    {
        int length = arr.length;

        for (int i = 0; i < length - 1; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                return false;
            }
        }

        return true;
    }
}

Answer 1

For the following code, pass in A as the original array and B as the sorted array.

---

CheckSingleSwap:

Instead of adding the indices to another list, store the first swap you encounter, and keep going; if you find the corresponding other swap, then store it and record the finding; if you find a different swap, exit with false. At the end if you've recorded the finding, print the corresponding indices.

private static boolean CheckSingleSwap(int[] A, int[] B)
{
    int L = A.length;
    int firstSwap = -1, secondSwap = -1;
    for(int i = 0; i < L; i++)
    {
        if(A[i] != B[i])
        {
            if (firstSwap == -1)
                firstSwap = i;
            else if (secondSwap == -1 && A[i] == B[firstSwap] && A[firstSwap] == B[i])
                secondSwap = i;
            else
                return false;
        }
    }
    if (firstSwap != -1 && secondSwap != -1)
    {
        System.out.println("yes");
        System.out.println("swap " + (firstSwap + 1) + " " + (secondSwap + 1));
        return true;
    }
    System.out.println("array is already sorted!");
    return false; // or whatever you decide to do; maybe even an exception or enumerated type
}

---

CheckSingleReverse:

You are doing WAY too much here! You seem to be brute forcing every single possible case (at first glance).

What you can do instead is to find the region where all the numbers are different. If there are more than two of these, or two which are separated by more than one element, then return false immediately.

The reason for the "more than one" thing above is because of odd-number length regions - the middle element would be the same. If you find such two regions, treat them as one. Then you can proceed to find out if the region is reversed.

private static boolean CheckSingleReverse(int[] A, int[] B)
{
    // find region
    int L = A.length;
    int diffStart = -1, diffEnd = -1; boolean mid = false, found = false;
    for (int i = 0; i < L; i++)
    {
        if (A[i] != B[i])
        {
            if (found)
            {
                if (i - diffEnd == 2 && !mid)
                {
                    mid = true;
                    found = false;
                    diffEnd = -1;
                }
                else
                    return false;
            }
            else if (diffStart == -1)
                diffStart = i;
        }
        else 
        if (diffStart != -1 && diffEnd == -1)
        {
            found = true;
            diffEnd = i - 1;
        }
    }
    if (diffEnd == -1)
    {
        if (A[L - 1] != B[L - 1])
            diffEnd = L - 1;
        else if (!found)
        {
            System.out.println("array is already sorted!");
            return false;
        }
    }

    // find out if it's reversed
    int count = (diffEnd - diffStart + 1) / 2;
    for (int i = 0; i < count; i++)
    {
        int oneEnd = diffStart + i, otherEnd = diffEnd - i;
        if (!(A[oneEnd] == B[otherEnd] && A[otherEnd] == B[oneEnd]))
            return false;
    }
    System.out.println("yes");
    System.out.println("reverse " + (diffStart + 1) + " " + (diffEnd + 1));
    return true;   
}

---

Just to give you an idea of the performance boost, on ideone.com, with an array length of 150, the original implementation of CheckSingleReverse took 1.83 seconds, whereas the new one took just 0.1 seconds. With a length of 250, the original actually exceeded the computational time limit (5 seconds), whereas the new one still took just 0.12 seconds.

From this it would seem that your implementation takes exponential time, whereas mine is linear time (ignoring the sorting).

Funnily enough, with an array size of 3 million I'm still getting around 0.26 seconds (ideone's execution time fluctuates a bit as well, probs due to demand)