Check if reversing a sub-array make the array sorted

Optimized Approach - 1

An efficient approach for solving the above problem is to use sorting techniques. Here, we first create a copy of the original which we then sort. Then compare the two arrays to check if any required subarray exists. For sorting, we can use Merge sort. 

Steps of Algorithm

1. We begin by creating a copy of the original array and then sort it.
2. Now, compare the original array with the sorted array. Mark the first and the last index that does not match the two arrays.
3. If no such indices exist, then return true.
4. Else, the elements between the two indices found shall be in decreasing order in the original array. 
5. If the condition is not fulfilled, then we return false. Else we return true.

Pseudocode

temp = arr
sort(temp, temp + n)
front = -1
back = -1
for i = 0 to n:
	if arr[i]!=temp[i]:
		front = i
		break
for i = n-1 to 0:
	if arr[i]!=temp[i]:
		back = i
		break
if front is -1:
	return true
for i = front to back:
	if arr[front] < arr[front+1]:
		return false
return true

Implementation in C++

#include "bits/stdc++.h"
using namespace std;
void solve()
{  
    int arr[] = [1, 2, 3, 5, 4];
    int n = sizeof(arr)/sizeof(int);
   
    // Creating a temporary array
    int temp[n];
    for(int i = 0;i<n;i+=1){
        temp[i]=arr[i];
    }

    //Sorting the array.
    sort(temp, temp+n);
    int fr,bk;

    //Defining the front and back variables.
    fr = -1;bk = -1;
    for(int i = 0;i<n;i+=1){

        //Getting the front variable value.
        if(arr[i]!=temp[i]){
            fr = i;
            break;
        }
    }
   
    //If front doesn't exist, then the array is already sorted.
    if(fr == -1){
        cout<<"YES\n";
        return;
    }

    //Getting the value of back variable.
    for(int i = n-1;i>=0;i--){
        if(temp[i]!=arr[i]){
            bk = i;
            break;
        }
    }

    //Now, we check if the array between front and back variable
    //is sorted in descending order.
    for(int i = fr;i<bk;i++){
        //If not, therefore No single subarray exist.
        if(arr[i]<arr[i+1]){
            cout<<"NO\n";return;
        }
    }
    cout<<"YES\n";
}  
int main()
{
    solve();
    return 0;
}

Implementation in Python

def solve(arr, n):
    
    #Creating a temporary array
    temp = [0]*n
    for i in range(n):
        temp[i] = arr[i]
    
    #Sorting the array.
    temp.sort()
    
    #Defining the front and back variables
    global fr, bk
    fr = bk = -1
    
    #Getting the front variable value
    for i in range(n):
        if temp[i]!=arr[i]:
            fr = i
            break
    
    if fr == -1:
        print("YES")
        return
    
    #Getting the back variable value
    for i in range(n-1, -1, -1):
        if temp[i]!=arr[i]:
            bk = i
            break
    
    #If whole array is sorted
    if fr>=bk:
        print("YES")
        return
    
    #Now, we check if the array between front and back variable
    #is sorted in descending order.
    for i in range(fr, bk):
        if arr[i]<arr[i+1]:
            print("NO")
            return 
    
    print("YES")
    return
   


arr = [1, 2, 3, 5, 4];
n = len(arr)
solve(arr, n)

Output: 

Yes

Complexity Analysis

Time complexity: O(nlog(n))

The Time complexity for the above code can be broken down into two parts:

1. O(nlog(n)) : For sorting the array.
2. O(n): For copying the original and getting front and back indexes.

Therefore, final Time complexity is O(n) + O(nlog(n)) which comes out to be O(nlog(n)).

Space complexity: O(n)

As we create a new temp array for sorting purposes, the space complexity becomes O(n).

Also Read - Selection Sort in C

Optimized Approach - 2

A more efficient approach only includes a linear traversal of the array. If the given condition is to be fulfilled, then the array shall be divided into three parts:

1. Increasing with the minimal set elements in the array.
2. Decreasing segment
3. Again increasing with the maximum set of elements.

Steps of Algorithm

1. Start traversing the array. Now, check the index till where the first part of the array is increasing. Let this be ind. If ind is n, then return true.
2. Now, as we got the first part, we start looking for the next decreasing array segment. Again we traverse the array. Along with it, we also have to compare these elements with the prior segment. As we can only reverse a particular decreasing segment, the relative order of elements between the segments shall be maintained.
3. Similarly, we repeat the above process for the 3rd segment.

Pseudocode

# Find first increasing part
i = 1
for i in range(1, n):
	if arr[i - 1] is less than arr[i] :
	i is equal to n:
		return True
	else:
		break
		
#Finding the reversed part
j = i
while j less than n and arr[j] less than arr[j - 1]:
	if i greater than 1 and arr[j] less than arr[i - 2]):
		return False
	j += 1
	
If j is equal to n:
return True

#Finding the last increasing part
k = j

#To check that the last increasing part elements are greater than the first part.
if arr[k] is less than arr[i - 1]
	return False

while k greater than 1 and k less than n:
	if (arr[k] < arr[k - 1]):
		return False
	k += 1
return True

Implementation in C++

#include "bits/stdc++.h"
using namespace std;
void solve()
{  
    int arr[] = {1, 2, 3, 5, 4};
    int n = sizeof(arr)/sizeof(int);
   
    //First, we find the increasing array part.
    int i = 1;
    while(i<n){
        if(arr[i]<arr[i-1]){
            break;
        }
        i+=1;
    }

    //If we reach end, then yes.
    if(i == n){
        cout<<"YES\n";
        return;
    }

    //Now we find the next decreasing array.
    int j = i;
    while(j<n && arr[j]<arr[j-1]){
        if(i>1 && arr[j]<arr[i-2]){
            cout<<"NO\n";
            return;
        }
        j+=1;
    }

    //If we reach the end of array, the yes.
    if(j == n){
        cout<<"YES\n";
        return;
    }

    //Next, we find the third increasing array.
    int k = j;

    //Here we see that, if the elements here are greater than the
    //Middle segment.
    if(arr[k]<arr[i-1]){
        cout<<"NO\n";
        return;
    }
    while(k>1 && k<n){
        if(arr[k]<arr[k-1]){
            cout<<"NO\n";
            return;
        }
        k+=1;
    }
    cout<<"YES\n";
}  
int main()
{
    solve();
    return 0;
}

Output: 

Yes

Complexity Analysis

Time complexity: O(n)

As in the above approach, we use only a single loop for traversing the whole array. So the overall time complexity of the above approach is O(n).

Space complexity: O(1)

As no extra space has been used in the above approach, thus the space complexity of the above approach is O(1)

Must Read  C Program to Reverse a Number

Frequently Asked Questions

What are the different sorting algorithms that can be used in the above approach?

Apart from Merge sort, we can use Quicksort in the above problem, as it also gives O(nlog(n)) as its average time complexity. But, if we’ve used Bubble sort, Insertion sort, or selection sort, our time complexity would have become O(n2).

What is the difference between sort function used in Python and C++?

It is a built-in function of the algorithm header file that is used to organise containers such as arrays and vectors. Internally, Quick-sort is used to implement this function.

Python employs the Timsort algorithm. Timsort is a hybrid sorting algorithm that combines merge sort and insertion sort to produce good results on a wide range of real-world data.

What is the difference between sort and sorted function in Python?

Sort() sorts the list in place, changing its indexes and returning None, whereas sorted() returns a new sorted list while leaving the original list unaltered. Another distinction is that sorted() allows any iterable, whereas list only accepts a single iterable. Sort() is a list class method that can only be used with lists.

Conclusion

This article discussed the problem of checking if there exists a subarray that, when reversed, makes the whole array sorted. Once you are done with this, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. 

Recommended problems -

• Beautiful Array
• Product Array Puzzle

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

We hope that this blog has helped you increase your knowledge regarding such DSA problems, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"