Pancake Sort

Problem Statement

Sort an array using only prefix reversals ("flips"). Each flip reverses arr[0..i]. Return the sequence of flip sizes that sorts the array.

Example

Input:  [3, 2, 4, 1]
Output: a sequence of flips that yields [1, 2, 3, 4]

Approach

Repeatedly place the current maximum. For the unsorted prefix of size size, find the max’s index; flip it to the front (if not already there), then flip the whole prefix of length size to send the max to position size-1. Record each flip size.

Complexity

• Time: O(n^2)
• Space: O(1) extra (plus the output list)

Solution Code

Python

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

Java

List<Integer> pancakeSort(int[] arr) {
    List<Integer> res = new ArrayList<>();
    for (int size = arr.length; size > 1; size--) {
        int mi = 0;
        for (int i = 1; i < size; i++) if (arr[i] > arr[mi]) mi = i;
        if (mi != size - 1) {
            if (mi != 0) { res.add(mi + 1); flip(arr, mi); }
            res.add(size); flip(arr, size - 1);
        }
    }
    return res;
}
void flip(int[] a, int k) {
    for (int i = 0, j = k; i < j; i++, j--) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

C++

void flip(vector<int>& a, int k) {
    for (int i = 0, j = k; i < j; i++, j--) swap(a[i], a[j]);
}
vector<int> pancakeSort(vector<int>& arr) {
    vector<int> res;
    for (int size = arr.size(); size > 1; size--) {
        int mi = 0;
        for (int i = 1; i < size; i++) if (arr[i] > arr[mi]) mi = i;
        if (mi != size - 1) {
            if (mi != 0) { res.push_back(mi + 1); flip(arr, mi); }
            res.push_back(size); flip(arr, size - 1);
        }
    }
    return res;
}

Key Takeaways

• Each round fixes one element using at most two flips.
• The allowed operation (prefix reversal) makes this a classic flip-sort puzzle.
• Reference: LeetCode 969 (Pancake Sorting).