969. Pancake Sorting

Given an array of integers arr, sort the array by performing a series of pancake flips.

In one pancake flip we do the following steps:

• Choose an integer k where 1 <= k <= arr.length.
• Reverse the sub-array arr[0…k-1] (0-indexed).

For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.

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.

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vector<int> res;
        vector<int> s = A;
        sort(begin(s), end(s));
        int i = A.size() - 1;
        while(i) {
            while(i and A[i] == s[i]) i--;
            if(!i) break;
            int pos;
            for(int j = 0; j < i; j++) {
                if(A[j] == s[i]) pos = j;
            }
            res.push_back(pos + 1);
            reverse(begin(A), begin(A) + pos + 1);
            res.push_back(i + 1);
            reverse(begin(A), begin(A) + i + 1);
        }
        return res;
    }
};