Sorting: Check if reversing sub array make the array sorted

Problem Statement:

You are given an array.

You need to check if reversing any sub array, can make the array sorted or not.

Example:

Input : arr [] = {1, 2, 5, 4, 3}
Output : Yes

By reversing {5, 4, 3}, array will be sorted.

Solution:

Sort the array.

Take two pointers, first pointer will point to the first of the mismatch.

Second pointer will point to the second of the mismatch, then reverse the subarray and compare with the original array and return the result.

Time Complexity: O(n * logn)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool solution(vector<int> &arr)
{
    vector<int> ans = arr ;
    sort(arr.begin(),arr.end()) ;

    int first_index=0 ;
    int second_index=0 ;
    
    for(int i=0; i<ans.size(); i++)
    {
        if(arr[i]!=ans[i])
        {
            first_index=i ;
            break ;
        }
    }
    
    for(int i=0; i < ans.size(); i++)
    {
        if(arr[i] != ans[i])
        {
            second_index=i ;
            
        }
    }
   
    reverse(ans.begin()+first_index,ans.begin()+second_index+1);
    
    if(ans==arr) return true ;

 return false ;   
}


int main()
{
    vector <int> arr = { 1, 2, 5, 4, 3 };
    
    if(solution(arr))
    {
    	cout<<"True";
    }
    else
    {
    	cout<<"False";
    }
    return 0;
}

Output

True