Check if reversing a sub array make the array sorted - GeeksforGeeks

Check if reversing a sub array make the array sorted - GeeksforGeeks
Given an array of distinct n integers. The task is to check whether reversing one sub-array make the array sorted or not. If the array is already sorted or by reversing a subarray once make it sorted, print "Yes", else print "No".

Method 1 (Simple : O(n2)
A simple solution is to consider every subarray one by one. Try reversing every subarray and check if reversing the subarray makes the whole array sorted. If yes, return true. If reversing any subarray doesn’t make the array sorted, then return false.

Method 2 (Sorting : O(nlogn)):
The idea is to compare the given array with the sorted array. Make a copy of the given array and sort it. Now, find the first index and last index which do not match with sorted array. If no such indices are found, print “Yes”. Else check if the elements between the indices are in decreasing order.

bool checkReverse(int arr[], int n)

{

    // Copying the array.

    int temp[n];

    for (int i = 0; i < n; i++)

        temp[i] = arr[i];

 

    // Sort the copied array.

    sort(temp, temp + n);

 

    // Finding the first mismatch.

    int front;

    for (front = 0; front < n; front++)

        if (temp[front] != arr[front])

            break;

 

    // Finding the last mismatch.

    int back;

    for (back = n - 1; back >= 0; back--)

        if (temp[back] != arr[back])

            break;

 

    // If whole array is sorted

    if (front >= back)

        return true;

 

    // Checking subarray is decreasing or not.

    do

    {

        front++;

        if (arr[front - 1] < arr[front])

            return false;

    } while (front != back);

 

    return true;

}

Read full article from Check if reversing a sub array make the array sorted - GeeksforGeeks