FastPrep
Problem

Minimum Operations to Sort a Permutation

FULLTIMEOA
See Amazon online assessment and hiring insights

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.

Examples
01 · Example 1
arr = [3,1,2]
return = 1

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

02 · 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].

03 · 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 problems
drafts saved locally
public int minOperationsToSortPermutation(int[] arr) {
  // write your code here
}
arr[3,1,2]
expected1
sign in to submit