FastPrepSort an Array with Rotate and Flip
Problem · Array

Sort an Array with Rotate and Flip

Learn this problem
● MediumAmazon logoAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

You are given an array values containing distinct integers. You may apply either of these operations:

  • Rotate: Move the first element to the end of the array.
  • Flip: Reverse the entire array.

Return the minimum number of operations needed to place values in strictly increasing order. You may use the operations in any sequence. If increasing order cannot be reached, return -1.

Function

minSortOperations(values: int[]) → int

Examples

Example 1

values = [3,4,1,2]return = 2

Rotate twice: [3,4,1,2] becomes [1,2,3,4]. No single operation produces increasing order.

Example 2

values = [3,2,1,4]return = 2

Flip to obtain [4,1,2,3], then rotate once to obtain [1,2,3,4].

Example 3

values = [1,3,2,4]return = -1

Rotations preserve the circular order, and a flip only reverses that order. Neither orientation can match [1,2,3,4], so sorting is impossible.

Constraints

  • 1 <= values.length <= 200000
  • Every element is a 32-bit signed integer.
  • All elements are distinct.

More Amazon problems

drafts saved locally
public int minSortOperations(int[] values) {
    // write your code here
}
values[3,4,1,2]
expected2
checking account