Sort array by reversing a specific segment of the array

Given an array Arr[ ] that consists of N distinct integers. Check that if it is possible to sort the array in ascending order by reversing a specific segment of the array. If it is possible then print the starting and the ending position of the segment. If it is not possible then print -1.

Given that the length of the segment may vary from 1 to N.
Reversing the segment of length 1 means the array remains unchanged after reversing.

Examples:

Input 	: N = 6
		  Arr[] = {1 , 2 , 3 , 4 , 5 , 6}
Output 	: YES
		  1 , 1
The array is already in sorted order. 
So we reverse the array segment starting 
and ending at 0th position to keep the
array as it is.
Input 	: N = 6
		  Arr[] = {6 , 4 , 5 , 2 , 3 , 1}
Output 	: NO
We cannot sort the array by reversing any of the possible
segments.
Input 	: N = 6
		  Arr[] = {1, 6 , 5 , 4 , 3 , 2}
Output 	: YES
		  2 , 6
Reversing the array from position 2 to position 6 will result a 
sorted array.

Approach :

Initialize the starting index where the array starts decreasing as -1 and the last index where the array stops decreasing as N .
Initialize a boolean named isIncreasing by true.
Traverse throughout the entire array and store the starting index where the array starts decreasing.
Store the next index where the array stops decreasing and break.
Reverse the array from the index where it starts decreasing to the next index where it stops decreasing.
Check if the array is sorted or not. If sorted then print the starting and ending positions else print no.
If the array never decreases then print 1 and 1 as the array is already sorted we will reverse any segment of length 1 to keep as it is.

Implementation in C++:

#include <bits/stdc++.h>

using namespace std;

void reverseSegment(int * arr, int n) {
  // Initialize the starting and ending position
  int st = -1;
  int en = n;

  // Initialize the boolean for isIncreasing
  bool isIncreasing = true;
  // Traverse throughout the array to get the
  // Starting and ending index of any decreasing sequence
  for (int i = 1; i < n; i++) {
    if (isIncreasing) {
      if (arr[i] < arr[i - 1]) {
        isIncreasing = false;
        st = i - 1;
      }
    } else {
      if (arr[i] > arr[i - 1]) {
        en = i;
        break;
      }
    }
  }

  bool isSorted = true;
  // Check if the array has no decreasing segments
  // That means it is already sorted
  if (st != -1) {
    // Reverse the array through decreasing segment
    reverse(arr + st, arr + en);
    // Check if the array is sorted
    for (int i = 1; i < n; i++) {
      if (arr[i] < arr[i - 1]) {
        isSorted = false;
        break;
      } else {
        isSorted = true;
      }
    }
  }

  // If the array is sorted
  if (isSorted) {
    cout << "yes\n";
    if (st == -1) {
      cout << "1 1\n";
    } else {
      cout << st + 1 << " " << en << "\n";
    }
  }
  // If the array is not sorted
  else {
    cout << "no\n";
  }
}

int main() {
  int n = 6;
  int arr[6]={1,6,5,4,3,2};
  reverseSegment(arr, n);
  return 0;
}

Output:

yes
2 6

Time Complexity: O(N)
Auxiliary Space: O(1)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.