1
class Solution {
2
 private:
3
  void reverse(vector<int> &arr, int start, int end) {
4
    while (start < end) {
5
      swap(arr[start++], arr[end--]);
6
    }
7
  }
8

9
 public:
10
  vector<int> pancakeSort(vector<int> &arr) {
11
    vector<int> copy = arr;
12
    sort(copy.begin(), copy.end());
13
    int end = copy.size() - 1;
14
    vector<int> ans;
15
    while (end > 0) {
16
      if (arr[end] != copy[end]) {
17
        int pos = end - 1;
18
        while (arr[pos] != copy[end]) {
19
          pos--;
20
        }
21
        reverse(arr, 0, pos);
22
        if (pos != 0) {
23
          ans.push_back(pos + 1);
24
        }
25
        reverse(arr, 0, end);
26
        ans.push_back(end + 1);
27
      }
28
      end--;
29
    }
30
    return ans;
31
  }
32
};