FastPrepMinimum Operations to Sort a Permutation

Minimum Operations to Sort a Permutation

Amazon logoAmazonFULLTIMEOA

Updated

Problem statement

You are given a permutation arr of size n, containing each integer from 1 to n exactly once.

In one operation, you may do either of the following:

  • Move the first element of the array to the end, shifting every other element one position to the left.
  • Reverse the entire array.

It is guaranteed that the array can be sorted into increasing order using these operations. Return the minimum number of operations needed to sort arr.

Function

minOperationsToSortPermutation(arr: int[]) → int

Examples

Example 1

arr = [3,1,2]return = 1

Move the first element 3 to the end to get [1,2,3].

Example 2

arr = [1,5,4,3,2]return = 2

Move 1 to the end to get [5,4,3,2,1], then reverse the array to get [1,2,3,4,5].

Example 3

arr = [1,2,3,4]return = 0

The array is already sorted.

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= arr.length
  • arr is a permutation of integers from 1 to arr.length.
  • It is guaranteed that arr can be sorted using the given operations.

More Amazon Online Assessment questions

Interview reports that mention this question

Amazon interview experiences

See Amazon hiring insights
Saved
class Solution {
    public int minOperationsToSortPermutation(int[] arr) {
      // write your code here
    }
}
Checking account…