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.

Recommended: Find number of common segments and its common point

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.