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 <= k <= arr.length.
Reverse the sub-array arr[1...k].

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 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.
 
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.
Notice that we return an array of the chosen k values of the pancake flips.

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.

 
Constraints:

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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Sorting

Amortized analysis

Greedy algorithms

Starter code: class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        

Solutions:
class Solution:

	def pancakeSort(self, A: List[int]) -> List[int]:
		n = len(A)
		res = []
		for x in range(n, 1, -1):
			idx = A.index(x)
			res.extend([idx + 1, x])
			A = A[idx::-1] + A[idx + 1:]
			A = A[x - 1::-1]
		return res


class Solution:

	def pancakeSort(self, A: List[int]) -> List[int]:
		N = len(A)
		res = []
		for x in range(N, 0, -1):
			i = A.index(x)
			res.extend([i + 1, x])
			A = A[:i:-1] + A[:i]
		return res


class Solution:

	def pancakeSort(self, arr: List[int]) -> List[int]:
		n = len(arr)
		ans = []
		for i in range(n, 0, -1):
			for j in range(i - 1):
				if arr[j] == i:
					ans.append(j + 1)
					ans.append(i)
					print((j, i))
					arr = list(reversed(arr[:j + 1])) + arr[j + 1:]
					print(arr)
					arr = list(reversed(arr[:i])) + arr[i:]
					print(arr)
					break
		return ans


class Solution:

	def pancakeSort(self, arr: List[int]) -> List[int]:
		res = []
		for x in range(len(arr), 1, -1):
			i = arr.index(x)
			res.extend([i + 1, x])
			arr = arr[:i:-1] + arr[:i]
		return res


class Solution:

	def pancakeSort(self, A: List[int]) -> List[int]:

		def flip(r):
			l = 0
			while l < r:
				(A[l], A[r]) = (A[r], A[l])
				(l, r) = (l + 1, r - 1)
		ans = []
		for x in range(len(A), 0, -1):
			i = A.index(x) + 1
			ans.extend([i, x])
			flip(i - 1)
			flip(x - 1)
		return ans


class Solution:

	def pancakeSort(self, arr: List[int]) -> List[int]:
		res = []
		for x in range(len(arr), 1, -1):
			i = arr.index(x)
			res.extend([i + 1, x])
			arr = arr[:i:-1] + arr[:i]
		return res
		out = []
		for i in range(len(arr), 0, -1):
			if arr[i - 1] != i:
				j = arr.index(i)
				out.extend([j + 1, i])
				arr[:j + 1] = reversed(arr[:j + 1])
				arr[:i] = reversed(arr[:i])
		return out


class Solution:

	def pancakeSort(self, arr: List[int]) -> List[int]:
		last = len(arr)
		ans = []
		while last > 1:
			max_pos = 0
			max_v = -float('inf')
			for i in range(last):
				if arr[i] > max_v:
					max_v = arr[i]
					max_pos = i
			ans.append(max_pos + 1)
			ans.append(last)
			arr[:max_pos + 1] = arr[:max_pos + 1][::-1]
			arr[:last] = arr[:last][::-1]
			last -= 1
		return ans


class Solution:

	def pancakeSort(self, arr: List[int]) -> List[int]:
		results = []
		end = len(arr)
		while end > 1:
			max_idx = arr.index(max(arr[:end]))
			if max_idx == end - 1:
				end -= 1
			else:
				if max_idx > 0:
					results.append(max_idx + 1)
					arr[:max_idx + 1] = reversed(arr[:max_idx + 1])
				results.append(end)
				arr[:end] = reversed(arr[:end])
				end -= 1
		print(arr)
		return results


class Solution:

	def pancakeSort(self, arr: List[int]) -> List[int]:
		n = len(arr)
		ans = []

		def flip(idx):
			arr[:idx + 1] = arr[:idx + 1][::-1]
		for i in range(len(arr)):
			maxInd = arr[:n].index(max(arr[:n]))
			if maxInd != n:
				ans.append(maxInd + 1)
				ans.append(n)
				flip(maxInd)
				flip(n - 1)
			n -= 1
		return ans


class Solution:

	def pancakeSort(self, arr: List[int]) -> List[int]:

		def flip(k):
			for i in range(k // 2):
				(arr[i], arr[k - i - 1]) = (arr[k - i - 1], arr[i])
		ans = []
		val = len(arr)
		while val > 0:
			i = arr.index(val)
			if 0 < i < val - 1:
				ans.append(i + 1)
				flip(i + 1)
			if i < val - 1:
				ans.append(val)
				flip(val)
			val -= 1
		return ans


class Solution:

	def pancakeSort(self, arr: List[int]) -> List[int]:

		def flip(sublist, k):
			i = 0
			while i < k / 2:
				(sublist[i], sublist[k - i - 1]) = (sublist[k - i - 1], sublist[i])
				i += 1
		ans = []
		value_to_sort = len(arr)
		while value_to_sort > 0:
			index = arr.index(value_to_sort)
			if index != value_to_sort - 1:
				if index != 0:
					ans.append(index + 1)
					flip(arr, index + 1)
				ans.append(value_to_sort)
				flip(arr, value_to_sort)
			value_to_sort -= 1
		return ans