Last Updated: 19 Oct, 2021

Sort Array

Easy

Asked in companies

Solve now

Problem statement

You are given ‘N’ distinct integers in the form of an array ‘ARR’. You need to find whether it is possible to sort the given array by choosing a continuous subarray and reversing that subarray. You have to return “true” if it is possible to sort the array after reversing the subarray. Otherwise, return “false”.

For example:

Let ‘ARR’ be: [3, 2, 1]
We can pick the whole array as a subarray and reverse it to get the sorted array [1, 2, 3].

Input Format :

The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains a single integer ‘N’, representing the size of the array.

The second line of each test case contains ‘N’ space-separated integers, representing the array ‘ARR’ elements.

Output Format :

For each test case, print ‘true’ if it is possible to sort the array after reversing the subarray, else print ‘false’.

Print output of each test case in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^6
1 <= ARR[i] <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to reverse all the possible subarrays and check if the array is sorted or not. If the array is sorted, we simply return true. Else we again reverse that subarray to get back the original array and check for other subarrays possible.

Here is the algorithm:

Run a loop from 0 to ‘N’ (say, iterator ‘i’)
- Run a loop from 0 to ‘N’ (say, iterator ‘j') to create a subarray from ‘i’ to ‘j’.
  - Create a variable (say, ‘FLAG’) that will check whether the array is sorted or not and initialize it with 0.
  - Reverse the subarray from index ‘i’ to ‘j’.
  - Check if the array is sorted or not by checking adjacent elements, if not update ‘FLAG’ by 1.
  - Check if ‘FLAG’ is equal to 0, return ‘true’.
  - Else, reverse the subarray from index ‘i’ to ‘j’ again to get the original array back.
Finally, return ‘false’.

Solve now

02 Approach

The basic idea is to find the first subarray that needs to be reversed to get the sorted array. We reverse the chosen subarray and check whether the array is sorted or not. If it is sorted, we print the range, and else the array cannot be sorted.

Here is the algorithm :

Create a variable (say, ‘i’) that will store the starting index of the subarray and initialize it with 0.
Run a loop till ‘i’ < ‘N’ - 1 and ‘ARR[i]’ < ‘ARR[i + 1]’
- Increment ‘i’ by 1.
Create a variable (say, ‘j’) that will store the ending index of the subarray and initialize it with ‘i’.
Run a loop till ‘j’ < ‘N’ - 1 and ‘ARR[j]’ > ‘ARR[j + 1]’
- Increment ‘j’ by 1.
Reverse the subarray from index ‘i’ to ‘j’.
Run a loop from 0 to ‘N’ - 1 (say, iterator ‘i’)
- Check whether ‘ARR[i]’ > ‘ARR[i + 1]’
  - Return ‘false’.
Return ‘true’.

Solve now