Pancake Sorting
Given an array of integers arr, sort the array by performing a series of pancake flips.
In one pancake flip, do the following steps:
- Choose an integer
kwhere1 <= k <= arr.length. - Reverse the sub-array
arr[0...k-1](0-indexed).
Return an array of the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.
Example 1
Input
arr = [3,2,4,1]Output
[4,2,4,3]We perform pancake flips with k values 4, 2, 4, and 3, transforming the array into [1, 2, 3, 4], which is sorted.
Example 2
Input
arr = [1,2,3]Output
[]The input is already sorted, so there is no need to flip anything.
Constraints
- 1 <= arr.length <= 100
- 1 <= arr[i] <= arr.length
- All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).