How do you solve Pancake Sorting?

Iterate from the full array size down to 2. For each size, find the max element's index in the prefix. If max is not at the end, flip the prefix up to max to bring it to front, then flip the prefix up to size to move it to its final position. Record each flip size. This approach sorts the array in at most 2n flips and runs in O(n^2) time due to scanning for max each iteration.

What pattern does Pancake Sorting use?

The Pattern: Greedy Algorithms (Greedy Placement via Reversal) The Heuristic: The optimal pancake sorting strategy greedily places the largest unsorted element at its correct position by at most two prefix reversals, reducing the problem size step-by-step until fully sorted.

Pancake Sorting | Greedy

Q: What is the time complexity of Pancake Sorting?

O(n^2). For each size from n down to 2, the algorithm scans the prefix to find the max element (O(n)) and performs up to two flips (each O(k) but bounded by n). This results in O(n^2) time overall.

Problem

Given an array of integers arr, return a sequence of pancake flips that sorts the array in ascending order, where a pancake flip reverses the order of the first k elements for some k.

1 ≤ arr.length ≤ 100
1 ≤ arr[i] ≤ arr.length
All integers in arr are unique

Example

Input: arr = [3,2,4,1]

Output: [4,2,4,3]

The algorithm sorts the array by repeatedly placing the largest unsorted element at its correct position. For the input [3,2,4,1], the largest element in the full array is 4 at index 2. First, flip the first 3 elements to bring 4 to the front: arr becomes [4,2,3,1]. Then flip the first 4 elements to move 4 to its final position: arr becomes [1,3,2,4]. Next, consider the first 3 elements [1,3,2]. The largest is 3 at index 1. Flip first 2 elements: arr becomes [3,1,2,4]. Flip first 3 elements: arr becomes [2,1,3,4]. Finally, sort the first 2 elements by flipping first 2 elements: arr becomes [1,2,3,4]. The sequence of flips is [3,4,2,3,2]. The output [4,2,4,3] is another valid sequence that achieves sorting.

Approach

Straightforward Solution

A brute-force approach would try all possible sequences of flips, which is combinatorially explosive and infeasible for arrays of even moderate size.

Core Observation

Each pancake flip reverses a prefix of the array, which can be used to move the largest unsorted element to its correct position by at most two flips: first flip to bring it to the front, second flip to move it to its final position.

Path to Optimal

Preview

The key insight is to sort the array from the largest element down to the smallest by repeatedly placing the largest unsorted element at its correct position. For each size from n down to 2, find the index of the largest element in the unsorted prefix…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate from the full array size down to 2. For each size, find the max element's index in the prefix…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

For each size from n down to 2, the algorithm scans the prefix to find the max element (O(n)) and performs up to two flips (each O(k) but bounded by n). This results in O(n^2) time overall.

Space

O(n)

The flips list stores up to 2n flip sizes, which is O(n) auxiliary space. The input array is modified in place, so no additional significant space is used.

Solution

Python

1class Solution:
  def pancakeSort(self, arr: list[int]) -> list[int]:
      flips = []
4
      def flip(end):
          left = 0
          right = end
8
          while left < right:
              arr[left], arr[right] = arr[right], arr[left]
              left += 1
              right -= 1
13
      for size in range(len(arr), 1, -1):
          max_index = 0
16
          for i in range(1, size):
              if arr[i] > arr[max_index]:
                  max_index = i
20
          if max_index == size - 1:
              continue
23
          if max_index != 0:
              flip(max_index)
              flips.append(max_index + 1)
27
          flip(size - 1)
          flips.append(size)
30
      return flips

Step-by-Step Solution

1

Accumulate Flip Operations and Define Prefix Reversal

3flips = []
5def flip(end):
  left = 0
  right = end
  while left < right:
      arr[left], arr[right] = arr[right], arr[left]
      left += 1
      right -= 1

Objective

To maintain a list of flip sizes and implement a helper function that reverses the prefix of the array up to a given index.

Key Insight

Recording flip sizes is essential to return the sequence of operations. The flip function reverses the prefix in place by swapping elements from the ends inward, enabling the core operation of pancake sorting. This abstraction cleanly separates the reversal logic from the sorting logic, improving clarity and correctness.

Interview Quick-Check

Core Logic

The flip function reverses the prefix of the array in place by swapping elements symmetrically from the start to the given end index.

State & Boundaries

The flips list records the sizes of each prefix reversal performed, which is the required output.

Common Pitfalls & Bugs

Forgetting to increment and decrement pointers correctly in the flip function can cause infinite loops or incorrect reversals.

2

Iteratively Place Largest Unsorted Element via Greedy Flips

To sort the array by repeatedly locating the largest unsorted element and moving it to its correct position using at most two flips.

3

Return the Sequence of Flip Sizes

To output the recorded sequence of flips that sorts the array.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 10 Critical

arr[left], arr[right] = arr[right], arr[left]

Swap elements at left and right pointers.

This line is the core reversal operation; swapping elements at the pointers progressively reverses the prefix in place, which is essential for the pancake flip.

Line 24 Critical

if max_index != 0:

Flip the prefix up to max_index to bring the largest element to the front.

This flip is critical because it brings the largest unsorted element to the front, enabling the subsequent flip to place it correctly at the end of the prefix.

Line 26 Critical

flips.append(max_index + 1)

Flip the entire prefix to move the largest element to its correct position.

This flip finalizes the placement of the largest element by reversing the entire prefix, moving it from the front to its sorted position.

Full line-by-line criticality + rationale for all 21 lines available on Pro.

Test Your Understanding

Why does flipping the largest unsorted element to the front before flipping the entire prefix guarantee progress towards sorting?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Pancake Sorting from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Pancake Sorting drill

or drill a free problem

1	`class Solution:`
2	`def pancakeSort(self, arr: list[int]) -> list[int]:`
3	`flips = []`
4
5	`def flip(end):`
6	`left = 0`
7	`right = end`
8
9	`while left < right:`
10	`arr[left], arr[right] = arr[right], arr[left]`
11	`left += 1`
12	`right -= 1`
13
14	`for size in range(len(arr), 1, -1):`
15	`max_index = 0`
16
17	`for i in range(1, size):`
18	`if arr[i] > arr[max_index]:`
19	`max_index = i`
20
21	`if max_index == size - 1:`
22	`continue`
23
24	`if max_index != 0:`
25	`flip(max_index)`
26	`flips.append(max_index + 1)`
27
28	`flip(size - 1)`
29	`flips.append(size)`
30
31	`return flips`

3	`flips = []`
5	`def flip(end):`
6	`left = 0`
7	`right = end`
9	`while left < right:`
10	`arr[left], arr[right] = arr[right], arr[left]`
11	`left += 1`
12	`right -= 1`