https://leetcode.com/problems/pancake-sorting

The idea is the following: first, put pancake with the biggest index on its place, then we never need to move it! Let us go through example: [3,2,4,6,5,1].

  1. We want to put pancake number 6 to the end, we can no do it immediatly, so let us put it to the beginning first: we need to flip first 4 pancakes: A = [6,4,2,3,5,1]. On the next step we can flip first 6 pancakes, so we have A = [1,5,3,2,4,6].
  2. Now, we want to put pancake number 5 to its place, we first flip first 2 pancakes to have [5,1,3,2,4,6] and then first 5, to have [4,2,3,1,5,6].
  3. Similar logic with number 4, but it is already in the beginning, so one step is enough: we flip first 4 pancakes to have [1,3,2,4,5,6].
  4. Put 3 to its place: flip first 2 to have [3,1,2,4,5,6] and then flip first 3 to have [2,1,3,4,5,6].
  5. Finally, put 2 on its place, flit first 2: we have [1,2,3,4,5,6].

So, our filps are the following: [4,6,2,5,4,2,3,2].

Comlexity: this is interesting part, we need to compute two types of complexities: classical one and how many flips we make. Note, that we make O(n) flips, because at each step we need to make no more than 2. Now, note, that on each step we make no more than O(n) operations, because we need to inverse some part of array. So, overall complexity will be O(n^2). Space complexity is O(n) to keep our answer.

class Solution:
    def pancakeSort(self, A):
        result, n = [], len(A)
        for i in range(n,0,-1):
            pl = A.index(i)
            if pl == i-1: continue
            if pl != 0:
                result.append(pl+1)
                A[:pl+1] = A[:pl+1][::-1]
            result.append(i)
            A[:i] = A[:i][::-1]
            
        return result

If you like the solution, you can upvote it on leetcode discussion section: Problem 0969