Problem

Given an array of integers arr, sort the array by performing a series of pancake flips.

In one pancake flip we do the following steps:

  • Choose an integer k where 1 <= k <= arr.length.
  • Reverse the sub-array arr[0...k-1] (0-indexed).

For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [_1_ ,_2_ ,_3_ ,4] after the pancake flip at k = 3.

Return an array of thek -values corresponding to a sequence of pancake flips that sortarr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation:
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [_1_ , _4_ , _2_ , _3_]
After 2nd flip (k = 2): arr = [_4_ , _1_ , 2, 3]
After 3rd flip (k = 4): arr = [_3_ , _2_ , _1_ , _4_]
After 4th flip (k = 3): arr = [_1_ , _2_ , _3_ , 4], which is sorted.

Example 2

1
2
3
4

Input: arr = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Constraints

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= arr.length
  • All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

Solution

Method 1 – Greedy Placement of Maximums

Intuition

Given an unsorted array, the goal is to sort it using only prefix reversals (flip operations). Unlike traditional sorting algorithms that minimize comparisons, pancake sorting aims to sort the array in as few reversals as possible. The process is similar to Selection Sort: we repeatedly place the maximum element at the end of the unsorted portion by flipping.

Approach

  1. Start with the current size equal to n and reduce it by one each time until it becomes 1.
  2. For each current size: a) Find the index of the maximum element in the unsorted part (arr[0..curr_size-1]). b) Flip the array up to that index to bring the maximum to the front. c) Flip the array up to the current size to move the maximum to its correct position at the end.
  3. Repeat until the array is sorted.

This approach ensures that each maximum is placed in its correct position with at most two flips per element.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> pancakeSort(vector<int>& arr) {
        vector<int> flips;
        for (int n = arr.size(); n > 1; --n) {
            int maxIdx = max_element(arr.begin(), arr.begin() + n) - arr.begin();
            if (maxIdx == n - 1) continue;
            if (maxIdx != 0) {
                reverse(arr.begin(), arr.begin() + maxIdx + 1);
                flips.push_back(maxIdx + 1);
            }
            reverse(arr.begin(), arr.begin() + n);
            flips.push_back(n);
        }
        return flips;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> flips = new ArrayList<>();
        for (int n = arr.length; n > 1; n--) {
            int maxIdx = 0;
            for (int i = 1; i < n; i++) {
                if (arr[i] > arr[maxIdx]) maxIdx = i;
            }
            if (maxIdx == n - 1) continue;
            if (maxIdx != 0) {
                flip(arr, maxIdx + 1);
                flips.add(maxIdx + 1);
            }
            flip(arr, n);
            flips.add(n);
        }
        return flips;
    }
    private void flip(int[] arr, int k) {
        for (int i = 0, j = k - 1; i < j; i++, j--) {
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def pancakeSort(self, arr: list[int]) -> list[int]:
        flips = []
        for n in range(len(arr), 1, -1):
            maxIdx = arr.index(max(arr[:n]))
            if maxIdx == n - 1:
                continue
            if maxIdx != 0:
                arr[:maxIdx+1] = arr[:maxIdx+1][::-1]
                flips.append(maxIdx+1)
            arr[:n] = arr[:n][::-1]
            flips.append(n)
        return flips

Complexity

  • ⏰ Time complexity: O(n^2), for each element we may scan the array and flip.
  • 🧺 Space complexity: O(n), for the output list