Check if given Array can be made Unsorted with a Single operation

Given an array of integers, in one operation a length x ( x >= 1 && x < n) can be chosen and the prefix of x length is sorted and then the suffix of (n – x) length is sorted independently of each other. The task is to check if the given array can be made unsorted by performing above operations exactly once.

Examples:

Input: arr[5] = [3,1,4,5,7]
Output: Yes
Explanation: 
Take x = 1, sort the prefix of length 1 and suffix of length 4, 
the final array becomes, [3, 1, 4, 5, 7]. 
Since the array can be made unsorted hence possible.

Input: arr[3] = [1, 2, 3]
Output: No
Explanation: 
Take any prefix of length 1 to (n-1) the array cannot be made unsorted.

Approach:
The problem divides into 2 cases:

Case-1: When given array is sorted: In this case aby perfix of length between 1 to arr.size() -1 will not give unsorted array.
Case-2: When array is not sorted: The answer would always exist as for index i < j, arr[i] > arr[j]. So take x = i and sort prefix of x length and then sort suffix of (n – x).

Implementation in C++:

//C++ implementation for above approach
#include <bits/stdc++.h>

using namespace std;

//function to check if unsorted array can be made or not 
bool possibleUnsorted(int arr[], int n) {

  //copy of array arr 
  int temp[n];

  for (int index = 0; index < n; index++) {
    temp[index] = arr[index];
  }
  //sort the temp array 
  sort(temp, temp + n);

  //if not same then it is possible 
  for (int index = 0; index < n; index++) {
    if (arr[index] != temp[index]) {
      return true;
    }
  }

  return false;
}
int main() {
  int arr1[5] = {3, 1, 4, 5, 7};
  int n1 = 5;

  if (possibleUnsorted(arr1, n1)) {
    cout << "Yes array can be made unsorted" << endl;
  } else {
    cout << "Array cannot be made unsorted" << endl;
  }
  int arr2[3] = {1, 2, 3};
  int n2 = 3;
  if (possibleUnsorted(arr2, n2)) {
    cout << "Yes array can be made unsorted" << endl;
  } else {
    cout << "Array cannot be made unsorted" << endl;
  }
}

Output:

Yes array can be made unsorted
Array cannot be made unsorted

Time complexity:

Copying the array takes O(n) time, where n is the array size.
Sorting the temporary array takes O(nlogn) time.
Comparing both arrays takes O(n) time. 
Overall time complexity is dominated by sorting, O(nlogn).

Space complexity:

Temporary array 'temp' takes O(n) space, where n is the array size.
The overall space complexity is O(n) due to the temporary array.

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.