Sort Array
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

Question

Sort Array

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

Accepted Answer

The question asks whether it is possible to sort an array by choosing a continuous subarray and reversing it.

Check if the array is already sorted. If yes, return true.
Find the first and last elements of the subarray that needs to be reversed.
Check if the subarray is in non-decreasing order. If yes, return true.
Check if the elements after the subarray are in non-increasing order. If yes, return true.
Otherwise, return false.

Accepted Answer

Use of sorting algorithms for this question

Accepted Answer

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:

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’.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(n^3)Explanation:

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).

Java (SE 1.8)

/*
	Time complexity: O(N^3)
	Space complexity: O(1)
	
	Where 'N' is the size of the array.
*/

public class Solution {

	public static void reversesubArray(int arr[], int start, int end) {

		while (start < end) {
			int temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;
			start++;
			end--;
		}

	}

	public static boolean sortArr(int n, int[] arr) {
		boolean ans = false;
        
		// Run loop to create all possible subarray.
		for (int i = 0; i < n; ++i) {
			for (int j = i; j < n; ++j) {

				// To check for sorted array.
				int flag = 0;

				// Reverse the subarray.
				reversesubArray(arr, i, j);

				// Check if array is sorted.
				for (int k = 0; k < n - 1; ++k) {

					// Check for condition.
					if (arr[k] > arr[k + 1]) {
						flag = 1;
					}
				}

				// Return true if array is sorted.
				if (flag == 0) {
					ans = true;
				}

				// Backtrack if array is not sorted.
				reversesubArray(arr, i, j);
			}
		}

		return ans;
	}

}

Python (3.5)

'''

	Time complexity: O(N^3)

    Space complexity: O(1)

    

    Where 'N' is the size of the array.

'''



from typing import *



def sortArr(n : int, arr: List[int]):

    

    # Run loop to create all possible subarray.

    for i in range(n):



        for j in range(i, n):

            

            # To check for sorted array.

            flag = 0

            

            # Reverse the subarray.

            arr[i: j + 1] = arr[i: j + 1][::-1]

            

            # Check if array is sorted.

            for k in range(n - 1):

                

                # Check for condition.

                if(arr[k] > arr[k + 1]):

                    flag = 1

                    break

            

            # Return true if array is sorted.

            if(flag == 0):

                return True

            

            # Backtrack if array is not sorted.

            arr[i: j + 1] = arr[i: j + 1][::-1]

            

    return False

C++ (g++ 5.4)

/*

	Time complexity: O(N^3)

    Space complexity: O(1)

    

    Where 'N' is the size of the array.

*/



bool sortArr(int n, vector &arr){

    

    // Run loop to create all possible subarray.

    for(int i = 0; i < n; ++i) {

        for(int j = i; j < n; ++j) {

            

            // To check for sorted array.

            int flag = 0;

            

            // Reverse the subarray.

            reverse(arr.begin() + i, arr.begin() + j + 1);

            

            // Check if array is sorted.

         	for(int k = 0; k < n - 1; ++k) {

                

                // Check for condition.

                if(arr[k] > arr[k + 1]) {

                    flag = 1;

                    break;

                }

            }

            

            // Return true if array is sorted.

            if(flag == 0) {

                return true;

            }

            

            // Backtrack if array is not sorted.

            reverse(arr.begin() + i, arr.begin() + j + 1);

        }

    }

    

    return false;

}

Accepted Answer

Greedy 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’.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(n)Explanation:

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

We iterate the ‘ARR’ to find the subarray. We also iterate ‘ARR’ to check whether the array is sorted or not. Therefore, the overall time complexity will be O(N).