# LeetCode 969: Pancake Sorting

## Problem Restatement

We are given an integer array `arr`.

A pancake flip chooses an integer `k` and reverses the first `k` elements of the array.

We need to return a sequence of `k` values that sorts the array in increasing order.

Any valid answer is accepted as long as it sorts the array using at most `10 * arr.length` flips.

The problem constraint gives `1 <= arr.length <= 100`, and `arr` is a permutation of the integers from `1` to `arr.length`. The operation reverses `arr[0...k-1]`. Source: LeetCode problem statement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `arr`, a permutation of `1` through `n` |
| Output | A list of flip sizes `k` |
| Operation | Reverse the prefix `arr[0:k]` |
| Requirement | Returned flips must sort the array |
| Limit | At most `10 * n` flips |

Example function shape:

```python
def pancakeSort(arr: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
arr = [3, 2, 4, 1]
```

One valid output is:

```python
[4, 2, 4, 3]
```

Explanation:

```python
[3, 2, 4, 1]
flip 4 -> [1, 4, 2, 3]
flip 2 -> [4, 1, 2, 3]
flip 4 -> [3, 2, 1, 4]
flip 3 -> [1, 2, 3, 4]
```

Example 2:

```python
arr = [1, 2, 3]
```

A valid output is:

```python
[]
```

The array is already sorted, so no flips are needed.

## First Thought: Use Normal Sorting

If we were only asked to return the sorted array, we could call:

```python
arr.sort()
```

But the problem asks for the operations that sort the array.

So we must build a sequence of prefix reversals.

## Key Insight

Use a selection-sort style idea.

Place the largest remaining value into its final position.

For an array of length `n`, the value `n` belongs at index `n - 1`.

We can move it there with at most two flips:

1. Flip it to the front.
2. Flip it from the front into its final position.

Example:

```python
arr = [3, 2, 4, 1]
```

The largest value is `4`, currently at index `2`.

First flip `3` elements:

```python
[3, 2, 4, 1] -> [4, 2, 3, 1]
```

Now `4` is at the front.

Then flip `4` elements:

```python
[4, 2, 3, 1] -> [1, 3, 2, 4]
```

Now `4` is fixed at the end.

Then repeat for `3`, then `2`, then `1`.

## Algorithm

Let `size` go from `len(arr)` down to `2`.

At each step:

1. The value `size` belongs at index `size - 1`.
2. Find the index of `size`.
3. If it is already at index `size - 1`, skip it.
4. If it is not at the front, flip `index + 1` to bring it to the front.
5. Flip `size` to move it into its final position.
6. Record each flip size.

Because each value needs at most two flips, the algorithm uses at most:

```python
2 * n
```

flips, which is within the allowed `10 * n` limit.

## Correctness

The algorithm processes target values from largest to smallest.

When processing `size`, all values greater than `size` have already been placed in their final positions at the end of the array.

The algorithm only flips prefixes of length at most `size`, so it never touches those already fixed values.

If `size` is not already in its final position, the first flip brings it to the front. The second flip reverses the first `size` elements, moving that front element to index `size - 1`, which is exactly its final sorted position.

After this step, value `size` is fixed permanently.

By repeating this for `size = n, n - 1, ..., 2`, every value is placed in its sorted position. Therefore, the returned flip sequence sorts the array.

## Complexity

Let `n = len(arr)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Each step searches for the target and reverses prefixes |
| Space | `O(n)` | The answer list stores flips |

The array is modified in place while building the result.

## Implementation

```python
class Solution:
    def pancakeSort(self, arr: list[int]) -> list[int]:
        flips = []

        for size in range(len(arr), 1, -1):
            index = arr.index(size)

            if index == size - 1:
                continue

            if index != 0:
                self.flip(arr, index + 1)
                flips.append(index + 1)

            self.flip(arr, size)
            flips.append(size)

        return flips

    def flip(self, arr: list[int], k: int) -> None:
        left = 0
        right = k - 1

        while left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
```

## Code Explanation

We store the answer here:

```python
flips = []
```

Then we process final positions from right to left:

```python
for size in range(len(arr), 1, -1):
```

Since `arr` is a permutation of `1` through `n`, the value `size` belongs at index `size - 1`.

Find it:

```python
index = arr.index(size)
```

If it is already fixed:

```python
if index == size - 1:
    continue
```

we do nothing.

If it is not at the front, bring it to the front:

```python
if index != 0:
    self.flip(arr, index + 1)
    flips.append(index + 1)
```

Then move it into its final position:

```python
self.flip(arr, size)
flips.append(size)
```

The helper reverses the first `k` elements in place:

```python
def flip(self, arr: list[int], k: int) -> None:
```

Finally:

```python
return flips
```

returns the sequence of operations.

## Testing

Because many valid flip sequences are accepted, tests should verify that the returned flips actually sort the array.

```python
def apply_flips(arr, flips):
    arr = arr[:]

    for k in flips:
        arr[:k] = reversed(arr[:k])

    return arr

def run_tests():
    s = Solution()

    arr = [3, 2, 4, 1]
    flips = s.pancakeSort(arr[:])
    assert apply_flips(arr, flips) == sorted(arr)
    assert len(flips) <= 10 * len(arr)

    arr = [1, 2, 3]
    flips = s.pancakeSort(arr[:])
    assert apply_flips(arr, flips) == sorted(arr)
    assert len(flips) <= 10 * len(arr)

    arr = [4, 3, 2, 1]
    flips = s.pancakeSort(arr[:])
    assert apply_flips(arr, flips) == sorted(arr)
    assert len(flips) <= 10 * len(arr)

    arr = [1]
    flips = s.pancakeSort(arr[:])
    assert apply_flips(arr, flips) == sorted(arr)
    assert len(flips) <= 10 * len(arr)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[3,2,4,1]` | Main example |
| `[1,2,3]` | Already sorted |
| `[4,3,2,1]` | Reverse order |
| `[1]` | Minimum input |