## Algorithm

Problem Name: 969. Pancake Sorting

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[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.

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.
```

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`).

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List pancakeSort(int[] arr) {
List result = new ArrayList<>();
for (int i = arr.length; i > 0; i--) {
int idx = findIdx(arr, i);
if (idx != i - 1) {
if (idx != 0) {
flip(arr, idx + 1);
}
flip(arr, i);
}
}
return result;
}

private void flip(int[] arr, int k) {
for (int i = 0; i < k / 2; i++) {
int temp = arr[i];
arr[i] = arr[k - i - 1];
arr[k - i - 1] = temp;
}
}

private int findIdx(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
}
``````
Copy The Code &

Input

cmd
arr = [3,2,4,1]

Output

cmd
[4,2,4,3]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const pancakeSort = function (arr) {
const res = []
let n = arr.length
while(n) {
const idx = indexOf(0, n - 1, n)
if(idx === n - 1) {
n--
} else {
flip(0, idx)
flip(0, n - 1)
res.push(idx + 1, n)
n--
}
}
return res

function flip(l, r) {
while(l < r) {
const tmp = arr[l]
arr[l] = arr[r]
arr[r] = tmp
l++
r--
}
}

function indexOf(start, end, target) {
let res = -1
for(let i = start; i <= end; i++) {
if(arr[i]===target) {
res = i
break
}
}
return res
}
}
``````
Copy The Code &

Input

cmd
arr = [3,2,4,1]

Output

cmd
[4,2,4,3]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def pancakeSort(self, A):
res = []
for x in range(len(A), 1, -1):
i = A.index(x)
res.extend([i + 1, x])
A = A[:i:-1] + A[:i]
return res
``````
Copy The Code &

Input

cmd
arr = [1,2,3]

Output

cmd
[]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0969_PancakeSorting
{
public IList PancakeSort(int[] A)
{
var result = new List();
for (int x = A.Length; x > 0; x--)
{
int index = 0;
while (A[index] != x) index++;
if (index + 1 == x) continue;

Flip(A, index + 1);

Flip(A, x);
}

return result;
}

private void Flip(int[] a, int k)
{
for (int i = 0, j = k - 1; i < j; i++, j--)
{
var temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
``````
Copy The Code &

Input

cmd
arr = [1,2,3]

Output

cmd
[]