Check if reversing a sub array make the array sorted Medium 0 attempts
GeeksforGeeks ↗

Check if reversing a sub array make the array sorted

Medium Sorting&Searching GeeksforGeeks

You're given an array. Determine whether picking a single contiguous subarray and reversing just that portion is enough to make the whole array sorted.

Input Format
Implement canSortByReversing(arr). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
arr = [1,2,5,4,3]
Output
true

Example 2

Input
arr = [1,2,3,4]
Output
true

Example 3

Input
arr = [1,3,2,2,4]
Output
true
Constraints
  • 1 <= N <= 10^5
Test Cases (3)
Case 1
Args: [[1,2,5,4,3]] Expected: true
Case 2
Args: [[1,2,3,4]] Expected: true
Case 3
Args: [[1,3,2,2,4]] Expected: true
Topics
Sorting&Searching

Compare with the Sorted Order

Find the first and last indices that differ from a sorted copy. If one reversal can sort the array, reversing that complete interval must produce the sorted order. This also handles duplicate values at the interval boundaries.

javascript
function canSortByReversing(arr) {
  const sorted = [...arr].sort((a,b)=>a-b);
  let left = 0, right = arr.length - 1;
  while (left < arr.length && arr[left] === sorted[left]) left++;
  while (right > left && arr[right] === sorted[right]) right--;
  for (let i = left; i <= right; i++) if (arr[left + right - i] !== sorted[i]) return false;
  return true;
}

Time: O(n log n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript