# 969. Pancake Sorting¶

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: vector pancakeSort(vector& arr) { vector ans; for (int target = arr.size(); target >= 1; --target) { int index = find(arr, target); reverse(arr.begin(), arr.begin() + index + 1); reverse(arr.begin(), arr.begin() + target); ans.push_back(index + 1); ans.push_back(target); } return ans; } private: int find(vector& arr, int target) { for (int i = 0; i < arr.size(); ++i) if (arr[i] == target) return i; throw; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public List pancakeSort(int[] arr) { List ans = new ArrayList<>(); for (int target = arr.length; target >= 1; --target) { int index = find(arr, target); reverse(arr, 0, index); reverse(arr, 0, target - 1); ans.add(index + 1); ans.add(target); } return ans; } private int find(int[] arr, int target) { for (int i = 0; i < arr.length; ++i) if (arr[i] == target) return i; throw new IllegalArgumentException(); } private void reverse(int[] arr, int l, int r) { while (l < r) swap(arr, l++, r--); } private void swap(int[] arr, int l, int r) { int temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def pancakeSort(self, arr: List[int]) -> List[int]: ans = [] for target in range(len(arr), 0, -1): index = arr.index(target) arr[:index + 1] = arr[:index + 1][::-1] arr[:target] = arr[:target][::-1] ans.append(index + 1) ans.append(target) return ans