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

Given an array, check if it can be sorted by reversing exactly one subarray.

Example: arr = [1, 2, 5, 4, 3] → Output: true (reverse subarray [5,4,3])

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

Find Unsorted Window

Find the first and last position where the array deviates, check if reversing makes it sorted.

function canSortByReversing(arr) {
  const n = arr.length;
  let i = 0;
  while (i < n - 1 && arr[i] <= arr[i+1]) i++;
  if (i === n - 1) return true;
  let j = n - 1;
  while (j > 0 && arr[j] >= arr[j-1]) j--;
  const reversed = [...arr.slice(0, i), ...arr.slice(i, j+1).reverse(), ...arr.slice(j+1)];
  for (let k = 0; k < n - 1; k++) if (reversed[k] > reversed[k+1]) return false;
  return true;
}

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

Saved in this browser only. Private to you.

JavaScript