Pancake Sorting: Sorting by Prefix Reversals

LeetCode Pancake Sorting (Problem 969) asks you to sort an array using only pancake flips. A pancake flip chooses a positive integer k (where k is at most arr.length), then reverses the subarray arr[0..k-1]. Your job is to return a sequence of flip values that sorts the array.

The problem

You are given an array of unique integers. The only operation you can perform is a pancake flip: pick a number k, and reverse the first k elements. You need to return a list of k values that, when applied in order, sort the array. The answer does not need to be the shortest sequence, but it must use at most 10 * arr.length flips.

Think of it like a stack of pancakes of different sizes. You can slide a spatula under any pancake and flip the entire stack above it. The goal is to arrange all the pancakes from smallest (top) to largest (bottom).

The approach

The strategy mirrors selection sort, but adapted for the constraint that you can only reverse prefixes.

For each round, you work from the largest unsorted element down to the smallest. To place element size in its correct position at index size - 1:

1. Find where size currently sits in the unsorted portion.
2. If it is already in the right place, skip it.
3. If it is not at the front, flip it to index 0 by reversing the prefix up to its current position.
4. Then flip the entire unsorted portion to send it to the back of that portion, which is its correct final position.

Each element takes at most two flips to land in its final spot. After placing it, you shrink the unsorted window by one and repeat.

Step-by-step walkthrough

Let's trace through arr = [3, 2, 4, 1] to see how pancake sorting works in practice.

Notice the pattern: in each round, the largest remaining element gets flipped to the front, then flipped down to its final position. The green cells are locked in place and never touched again.

The code

def pancakeSort(arr):
    result = []
    n = len(arr)
    for size in range(n, 1, -1):
        max_idx = arr.index(max(arr[:size]))
        if max_idx == size - 1:
            continue
        if max_idx != 0:
            result.append(max_idx + 1)
            arr[:max_idx + 1] = arr[:max_idx + 1][::-1]
        result.append(size)
        arr[:size] = arr[:size][::-1]
    return result

The outer loop counts down from n to 2. In each iteration, size represents the length of the unsorted portion. You find the index of the maximum element within that portion using arr.index(max(arr[:size])).

If the max is already at position size - 1, it is in its final spot and you skip the round. Otherwise, if the max is not at index 0, you flip it to the front first. Then you flip the entire unsorted prefix of length size to send the max to the end of the unsorted section.

The result list accumulates all the flip values in order. Each append records one flip operation.

Complexity analysis

The outer loop runs n - 1 times. Inside each iteration, finding the maximum takes O(size) time, and each reversal takes O(size) time. Since size ranges from n down to 2, the total work is O(n + (n-1) + ... + 2) = O(n^2).

The space is O(n) for the result list that stores the flip sequence. The sorting itself is done in-place on the input array.

The building blocks

Selection sort variant

The core idea is the same as selection sort: repeatedly find the largest remaining element and place it in its correct position. In regular selection sort, you swap the element directly. In pancake sorting, you achieve the same placement through two prefix reversals. Recognizing this connection helps you derive the algorithm from scratch rather than memorizing it.

Prefix reversals

A prefix reversal is a restricted operation: you can only reverse elements starting from the beginning of the array. This constraint forces creative thinking. You cannot move a single element to an arbitrary position. Instead, you use the "flip to front, then flip to target" two-step pattern. This same idea of working within constrained operations appears in problems like Rotate Array, where you use reversals to achieve rotations.

Edge cases

• Already sorted array. The algorithm detects when each max is already in position (max_idx == size - 1) and skips those rounds. The result list will be empty or very short.
• Two-element array. At most one flip is needed. If arr[0] is greater than arr[1], one flip of size 2 sorts it. Otherwise, no flips are needed.
• Reverse-sorted array. This is the worst case in terms of flips. Every round needs both flips because the max is never in the right position, producing exactly 2 * (n - 1) flip values.
• Single-element array. The loop never executes because range(1, 1) is empty. The function returns an empty list, which is correct.

From understanding to recall

The key to internalizing pancake sorting is the two-flip pattern: flip the target to the front, then flip the whole unsorted prefix to send it to the back. Once that pattern is second nature, the rest of the algorithm follows from selection sort logic.

When you review this problem, trace through a small example by hand. Write out the array after every flip. Pay attention to how the "sorted tail" grows by one element each round. That visual pattern is what you want burned into memory, not the code itself.

The code is short enough that you can reconstruct it from the algorithm description. Practice writing it from scratch a few times. Focus on getting the loop bounds right (range(n, 1, -1)) and the flip indexing correct (max_idx + 1 vs size). Those details trip people up when they try to recall the solution under pressure.

Related posts

• Sort Colors - Another in-place sorting problem with constrained operations
• Sort an Array - General sorting strategies and their tradeoffs
• Rotate Array - Array manipulation through reversals, a closely related technique