Sort Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
11 upvotes
Asked in companies
IntuitAdobeErnst & Young (EY)

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
3 2 1
4
2 1 3 4
Sample Output 1 :
true
true
Explanation For Sample Input 1 :
For test case 1: 
We can pick the whole array as a subarray and reverse it to get the sorted array [1, 2, 3].

For test case 2: 
We can pick the subarray from index 1 to 2, i.e., [2, 1], and reverse it to get a sorted array [1, 2, 3, 4].
Sample Input 2 :
2
2 
1 2
4
3 1 2 4
Sample Output 2 :
true
false
Hint

Try to reverse all possible subarrays.

Approaches (2)
Brute Force

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:

 

  1. 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.
  2. Finally, return ‘false’.
Time Complexity

O(N^3), where ‘N’ is the size of the array.

 

We iterate through each subarray that takes O(N ^ 2) of time and for each subarray, we reverse it and check whether the array is sorted or not which takes O(N) of time. Therefore, the overall time complexity will be O(N^3).

Space Complexity

O(1).

 

We don't use any extra space. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Sort Array
Full screen
Console