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

Example function shape:

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

Examples

Example 1:

arr = [3, 2, 4, 1]

One valid output is:

[4, 2, 4, 3]

Explanation:

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

arr = [1, 2, 3]

A valid output is:

[]

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:

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:

arr = [3, 2, 4, 1]

The largest value is 4, currently at index 2.

First flip 3 elements:

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

Now 4 is at the front.

Then flip 4 elements:

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

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

The array is modified in place while building the result.

Implementation

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:

flips = []

Then we process final positions from right to left:

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:

index = arr.index(size)

If it is already fixed:

if index == size - 1:
    continue

we do nothing.

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

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

Then move it into its final position:

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

The helper reverses the first k elements in place:

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

Finally:

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.

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: