1
class Solution:
2
    def pancakeSort(self, arr: List[int]) -> List[int]:
3
        # helper function to flip the numbers in the array
4
        def flip(i, j):
5
            while i < j:
6
                arr[i], arr[j] = arr[j], arr[i]
7
                j -= 1
8
                i += 1
9

10
        # sort from 0 to i
11
        def sort(i):
12
            # base case where all the numbers are sorted, thus no more recursive calls
13
            if i < 0:
14
                return []
15
            ret = []
16
            # find the biggest number, which always will be the len(arr), or i + 1
17
            idx = arr.index(i + 1)
18
            # 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
19
            if idx == i:
20
                return sort(i - 1)
21

22
                # 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
23
            ret.append(idx + 1)
24
            flip(0, idx)
25
            # 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)
26
            ret.append(i + 1)
27
            flip(0, i)
28
            # sort the next biggest number by setting a new boundary i - 1
29
            return ret + sort(i - 1)
30

31
        return sort(len(arr) - 1)