vikas83's blog

By vikas83, history, 2 months ago, In English

This problem asks whether an array can be sorted by reversing at most one continuous segment.

Key observation: If the array can be sorted using exactly one reverse, then the array must contain only ONE continuous decreasing segment. More than one such segment makes it impossible.

Approach: 1. Traverse the array to find the first index l where a[l] > a[l+1]. 2. If no such index exists, the array is already sorted. Answer is YES with segment (1, 1). 3. Starting from l, extend to the right while the sequence keeps decreasing to find r. 4. Reverse the segment [l, r]. 5. Check whether the array is sorted after the reversal.

If it is sorted, print YES and (l+1, r+1). Otherwise, print NO.

Why this works: A sorted array is non-decreasing. One reverse can only fix one decreasing interval. If reversing that interval does not fix the array, no other single reverse can.

Time Complexity: O(n), since we scan the array a constant number of times.

This greedy observation makes the problem straightforward once the decreasing segment is identified.

Full text and comments »

  • Vote: I like it
  • -23
  • Vote: I do not like it