## Introduction

In this blog, we will be discussing the problem of checking if there exists a certain subarray that, when reversed, makes the whole array sorted. For this, we have used three approaches:

- Brute force: Here, we will use a naĂŻve approach with two loops. We check for each subarray.
- Sorting based: This is an efficient approach that uses the concept of sorting. However, the space complexity here is O(n).
- Linear approach: This is the most efficient approach for this problem. Here the time complexity is O(n) while the space complexity is O(1).

### Problem Statement

The problem above states that given an array of elements, we have to check if reversing any subarray makes the collection sorted.

### Sample Example

**Input 1: **

`arr[] = {1, 2, 3, 6, 5 }`

**Output 1: **

`Yes`

**Explanation:** In the above array, reversing the [6 5] subarray makes the array sorted.

**Input 2: **

`arr[] = {5, 9, 7, 3, 1}`

**Output 2: **

`No`

**Explanation:** As in the above array, there exists no such subarray which can be reversed to make the array sorted.

## Brute Force Approach

Below is the brute force approach:

- Check for every subarray by reversing it.
- If the array becomes sorted for any subarray being reversed, return true.
- If no such subarray

### Pseudocode

```
For i = 0 to n:
For j = 0 to i:
reverse the subarray arr[i:j]
if the array becomes sorted:
return true
If no such subarray exist:
return false
```

### 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);
//Traversing the loop for getting a subarray.
for(int i = 0;i<n;i+=1){
for(int j = i;j<n;j+=1){
int l = i;int r = j;
//Now, for each subrarray from arr[i..j], we reverse
//To check if this is the one.
while(r>l){
swap(arr[l], arr[r]);
r-=1;l+=1;
}
//Checking if reversing makes it sorted.
bool sorted = true;
for(int j = 1;j<n;j+=1){
if(arr[j]<arr[j-1]){
sorted=false;
break;
}
}
//If yes, we return true;
if(sorted){
cout<<"YES\n";return;
}
//We readjust the subarray if the array ain't sorted.
l=i;r=j;
while(r>l){
swap(arr[l], arr[r]);
r-=1;l+=1;
}
}
}
cout<<"NO\n";
}
int main()
{
solve();
return 0;
}
```

### Implementation in Python

```
def solve(arr, n):
for i in range(n):
for j in range(i):
#Here, we are using another array for storing the reversed subarray. Therefore
#Space Complexity is O(n)
reversed_list= arr[0:i] + arr[j:i-1:-1] + arr[j+1:]
#Checking if the reversing the subarray made the whole array sorted
f = True
for j in range(1, n):
if reversed_list[j]<reversed_list[j-1]:
f = False
break
#If sorted, then yes.
if f:
print("YES")
return
#If not sorted, we print No
print("NO")
arr = [1, 2, 3, 5, 4]
n = len(arr)
solve(arr, n)
```

**Output: **

`Yes`

**Complexity Analysis**

**Time complexity: O(n ^{2})**

As in the above approach, we use two nested loops of size n, and the time complexity for the above approach becomes O(n^{2})

**Space complexity: O(1)**

As in the above approach to solve the problem, we havenâ€™t used any extra space for solving it. Therefore, the space complexity is O(1), i.e. constant.

Read More - __Time Complexity of Sorting Algorithms____ __and __Euclid GCD Algorithm__