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 &lt;= k &lt;= 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.

&nbsp;
Example 1:

Input: arr = [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: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.


Example 2:

Input: arr = [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.


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 100
	1 &lt;= arr[i] &lt;= arr.length
	All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).


class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        #helper function to flip the numbers in the array
		def flip(i, j):
            while i < j:
                arr[i], arr[j] = arr[j], arr[i]
                j -= 1
                i += 1
        
        #sort from 0 to i
        def sort(i):
			#base case where all the numbers are sorted, thus no more recursive calls
            if i < 0:
                return []
            ret = []
			#find the biggest number, which always will be the len(arr), or i + 1
            idx = arr.index(i + 1)
			# if the biggest number is in the right place, as in idx == i, then we don't change anything, but just move to sort the next biggest number
            if idx == i:
                return sort(i - 1)
            
			#we flip it with the first element (even if the biggest number is the first element, it will flip itself (k = 1) and does not affect the result
            ret.append(idx + 1)
            flip(0, idx)
			#we know the biggest number is the first element of the array. Flip the whole array in the boundary so that the biggest number would be in the last of the subarray (notice not len(arr) - 1 because that will flip the already-sorted elements as well)
            ret.append(i + 1)
            flip(0, i)
			#sort the next biggest number by setting a new boundary i - 1
            return ret + sort(i - 1)
            
            
        return sort(len(arr) - 1)
            
// BruteForce Approach!
// Author - Nikhil Sharma
// LinkedIn - https://www.linkedin.com/in/nikhil-sharma-41a287226/
// Twitter - https://twitter.com/Sharma_Nikh12

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        int n = arr.length;
        while(n!=1) {
            int maxIndex = findIndex(arr,n);
            reverse(arr, maxIndex);
            reverse(arr, n-1);
            list.add(maxIndex+1);
            list.add(n);
            n--;
        }
        return list;
    }

    static int findIndex(int[] arr, int value) {
        for(int i=0; i<arr.length; i++) {
            if(arr[i] == value){
                return i;
            }
        }
        return 0;
    }

    static void reverse(int[] arr, int maxIndex) {
        int l = 0;
        while(l<maxIndex) {
            int temp = arr[l];
            arr[l] = arr[maxIndex];
            arr[maxIndex] = temp;
            l++;
            maxIndex--;
        }
    }
}
class Solution {
private:
    void reverse(vector<int>&arr,int start,int end){
        while(start<end){
            swap(arr[start++],arr[end--]);
        }
    }
public:
    vector<int> pancakeSort(vector<int>& arr) {
        vector<int>copy=arr;
        sort(copy.begin(),copy.end());
        int end=copy.size()-1;
        vector<int>ans;
        while(end>0){
            if(arr[end]!=copy[end]){
                int pos=end-1;
                while(arr[pos]!=copy[end]){
                    pos--;
                }
                reverse(arr,0,pos);
                if(pos!=0){
                    ans.push_back(pos+1);
                }
                reverse(arr,0,end);
                ans.push_back(end+1);
            }
            end--;
        }
        return ans;
    }
};
var pancakeSort = function(arr) {
let res = [];

for(let i=arr.length; i>0; i--){//search the array for all values from 1 to n
    let idx = arr.indexOf(i);
    if(idx!=i-1){// if value is not present at its desired index
        let pancake = arr.slice(0,idx+1).reverse();//flip the array with k=index of value i to put it in front of the array
        res.push(idx+1);
        arr = arr.slice(idx+1);
        arr = pancake.concat(arr);//value i is now at index 0
        pancake = arr.slice(0,i).reverse();//flip the array with k = i-1 to put the value at its place
        res.push(i);
        arr = arr.slice(i);
        arr = pancake.concat(arr);//now the array is sorted from i to n
    }
}
return res;
};
Pancake Sorting