Pancake Sorting

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #simulation

Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: [3,2,4,1] Output: [4,2,4,3] Explanation: We perform 4 pancake flips, with k values 4, 2, 4, and 3. Starting state: A = [3, 2, 4, 1] After 1st flip (k=4): A = [1, 4, 2, 3] After 2nd flip (k=2): A = [4, 1, 2, 3] After 3rd flip (k=4): A = [3, 2, 1, 4] After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted.

Example 2:

Input: [1,2,3] Output: [] Explanation: The input is already sorted, so there is no need to flip anything. Note that other answers, such as [3, 3], would also be accepted.

Note:

- 1 <= A.length <= 100
- A[i] is a permutation of [1, 2, …, A.length]

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// https://code.dennyzhang.com/pancake-sorting // Basic Ideas: // Each round move the maximum to the head // Complexity: O(n*n), Space O(1) func pancakeSort(A []int) []int { res := []int{} B := make([]int, len(A)) for i:=len(A)-1; i>=0; i-- { k:=0 for j:=1; j<=i; j++ { if A[k] < A[j] { k = j } } if k != i { l:=0 for j:=i; j>k; j--{ B[l]=A[j] l++ } for j:=0; j<=k; j++ { B[l]=A[j] l++ } if k != 0 { res = append(res, k+1) } if i != 0 { res = append(res, i+1) } for j:=0; j<len(A); j++ { A[j] = B[j] } } } return res }