Pancake Sorting

medium array sorting reversal greedy

Problem

Given an array of integers arr, sort it using only pancake flips. A pancake flip of size k reverses the order of the first k elements (the prefix arr[0..k-1]). Return any sequence of flip sizes that sorts the array; the number of flips need not be minimal but must not exceed 10 * arr.length.

Inputarr = [3, 2, 4, 1]

Output[4, 2, 4, 3]

Flip 4 → [1,4,2,3], flip 2 → [4,1,2,3], flip 4 → [3,2,1,4], flip 3 → [1,2,3,4]. The array is sorted.

arr (comma-separated)

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

function pancakeSort(arr) {
  const res = [];
  const flip = (k) => { for (let l = 0, r = k - 1; l < r; l++, r--) [arr[l], arr[r]] = [arr[r], arr[l]]; };
  for (let size = arr.length; size > 1; size--) {
    let idx = 0;
    for (let j = 1; j < size; j++) if (arr[j] > arr[idx]) idx = j;
    if (idx === size - 1) continue;
    if (idx !== 0) { flip(idx + 1); res.push(idx + 1); }
    flip(size); res.push(size);
  }
  return res;
}

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> res = new ArrayList<>();
        for (int size = arr.length; size > 1; size--) {
            int idx = 0;
            for (int j = 1; j < size; j++) if (arr[j] > arr[idx]) idx = j;
            if (idx == size - 1) continue;
            if (idx != 0) { flip(arr, idx + 1); res.add(idx + 1); }
            flip(arr, size); res.add(size);
        }
        return res;
    }
    private void flip(int[] arr, int k) {
        for (int l = 0, r = k - 1; l < r; l++, r--) {
            int t = arr[l]; arr[l] = arr[r]; arr[r] = t;
        }
    }
}

vector<int> pancakeSort(vector<int>& arr) {
    vector<int> res;
    auto flip = [&](int k) { reverse(arr.begin(), arr.begin() + k); };
    for (int size = arr.size(); size > 1; size--) {
        int idx = 0;
        for (int j = 1; j < size; j++) if (arr[j] > arr[idx]) idx = j;
        if (idx == size - 1) continue;
        if (idx != 0) { flip(idx + 1); res.push_back(idx + 1); }
        flip(size); res.push_back(size);
    }
    return res;
}

Explanation

Imagine a stack of pancakes of different sizes; the only move you have is a prefix flip — stick a spatula in and reverse the first k pancakes. We sort the array using just these flips, placing the largest value last, then the next largest, and so on.

We loop with a shrinking window size from the full length down to 2. In each round we find the index of the maximum within arr[0..size-1]. That value needs to end up at position size - 1.

It takes at most two flips to put it there. First, if the max is not already at the front, flip the prefix of length idx + 1 to move it to index 0. Then flip the prefix of length size to send it to the back of the current window. We record each flip size in res.

If the max is already at size - 1, it is in place, so we skip it and shrink the window.

Example: arr = [3, 2, 4, 1]. The max 4 is at index 2. Flip 3 brings it to the front → [4, 2, 3, 1]; flip 4 sends it to the back → [1, 3, 2, 4]. Now the last slot is locked and we repeat on the smaller window until sorted.

Time: O(n²) Space: O(1)