Introducing the Pancake Sorting Algorithm

Given an array of integers A, We need to sort the array performing a series of pancake flips. In one pancake flip we do the following steps:

Choose an integer k where 0 <= k < A.length.
Reverse the sub-array A[0…k].
For example, if A = [3,2,1,4] and we performed a pancake flip choosing k = 2, we reverse the sub-array [3,2,1], so A = [1,2,3,4] after the pancake flip at k = 2.

Return an array of the k-values of the pancake flips that should be performed in order to sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:
Input: A = [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.
Notice that we return an array of the chosen k values of the pancake flips.

Example 2:
Input: A = [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.

Constraints:
1 ≪= A.length <= 100
1 <= A[i] <= A.length
All integers in A are unique (i.e. A is a permutation of the integers from 1 to A.length).

Pancake Sorting Algorithm

Pancake sorting algorithm may have different implementation. One simple method is to find the maximum element, then reverse the prefix subarray to make it to the begining. Then, we can reverse the whole (unsorted) part to make it to the end – which puts this number inplace. Then we have one less number to sort.

The following is the Python implementation of the pancake sorting algorithm. The time complexity is O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        k = len(A)
        ans = []
        while k > 0:
            i = A[:k].index(max(A[:k]))
            ans.append(i + 1)
            A = A[:i+1][::-1] + A[i+1:]
            ans.append(k)
            A = A[:k][::-1] + A[k:]
            k -= 1
        return ans

class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        k = len(A)
        ans = []
        while k > 0:
            i = A[:k].index(max(A[:k]))
            ans.append(i + 1)
            A = A[:i+1][::-1] + A[i+1:]
            ans.append(k)
            A = A[:k][::-1] + A[k:]
            k -= 1
        return ans

The C++ Pancake sorting algorithm implementation is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vector<int> res;
        int k = A.size();
        while (k > 0) {
            auto it = std::max_element(begin(A), begin(A) + k);
            int maxIndex = it - begin(A) + 1;
            // make max to the begining
            res.push_back(maxIndex);
            std::reverse(begin(A), it + 1);
            // make max to the end
            res.push_back(k);
            std::reverse(begin(A), begin(A) + k);
            k --;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vector<int> res;
        int k = A.size();
        while (k > 0) {
            auto it = std::max_element(begin(A), begin(A) + k);
            int maxIndex = it - begin(A) + 1;
            // make max to the begining
            res.push_back(maxIndex);
            std::reverse(begin(A), it + 1);
            // make max to the end
            res.push_back(k);
            std::reverse(begin(A), begin(A) + k);
            k --;
        }
        return res;
    }
};

The space complexity is O(N).

–EOF (The Ultimate Computing & Technology Blog) —