Sort Array by Reversing a Subarray

You are given an array of 'N' distinct integers, 'ARR'. Determine if it is possible to sort this array by selecting a continuous subarray and reversing it. Return 'true' if sorting is possible by this method, otherwise return 'false'.

Example:

Input:

ARR = [3, 2, 1]

Output:

true

Explanation:

The entire array can be reversed to get [1, 2, 3], which is sorted.

Input:

ARR = [1, 3, 2, 4]

Output:

true

Explanation:

Reversing the subarray [3, 2] results in the sorted array [1, 2, 3, 4].

Constraints:

1

Question

Sort Array by Reversing a Subarray

You are given an array of 'N' distinct integers, 'ARR'. Determine if it is possible to sort this array by selecting a continuous subarray and reversing it. Return 'true' if sorting is possible by this method, otherwise return 'false'.

Example:

Input:

ARR = [3, 2, 1]

Output:

true

Explanation:

The entire array can be reversed to get [1, 2, 3], which is sorted.

Input:

ARR = [1, 3, 2, 4]

Output:

true

Explanation:

Reversing the subarray [3, 2] results in the sorted array [1, 2, 3, 4].

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.

Sort Array by Reversing a Subarray

Example:

Input:

Output:

Explanation:

Input:

Output:

Explanation:

Constraints:

Unthinkable Solutions Software Developer interview questions & answers

Popular interview questions of Software Developer