Pancake Sorting solution and explanation
9 more videos on this problem
Pancake Sorting | LeetCode 969 | C++, Java, PythonKnowledge Center · 19:09 · 15K views
Leetcode - Pancake Sorting (Python)Timothy H Chang · 5:59 · 6K views
Google Coding Question - Pancake Sorting (Leetcode 969)Algorithms Casts · 17:47 · 5K views
Pancake Sorting | LeetCodeFaxMachine Codes · 11:44 · 3K views
pancake sorting leetcode | leetcode 969 | selection sort approachNaresh Gupta · 8:12 · 3K views
Pancake Sorting | Leet code 969 | Theory explained + Python codeSai Anish Malla · 11:55 · 2K views
LeetCode 969. Pancake SortingHappy Coding · 16:35 · 750 views
Daily Leetcode #151: Aug 29, 2020 - 969. Pancake SortingProgramming Live with Larry · 8:46 · 581 views
LC 969: Pancake Sorting, Part 1Dinesh Kumar · 4:41 · 565 views
Apple Coding Interview Question | Leetcode 969 | Pancake SortingWorkWithGoogler · 9:37 · 513 views
The 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
kwhere1 <= 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 the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.
Example 1:
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:
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 <= 1001 <= arr[i] <= arr.length- All integers in
arrare unique (i.e.arris a permutation of the integers from1toarr.length).
Approach overview
Problem Overview: You are given a permutation of integers from 1 to n. The only allowed operation is a pancake flip: reverse the order of the first k elements of the array. The goal is to return a sequence of flips that sorts the array in ascending order.
Approach 1: Brute Force Flip Simulation (O(n^3) time, O(1) space)
A naive way is to repeatedly check whether the array is sorted and try different prefix flips until the correct element moves to its position. Each operation requires reversing a prefix and scanning the array to verify order. Because every placement may require multiple trial flips and repeated scans, the total cost can grow to O(n^3). This approach mainly demonstrates how the flip operation works but is inefficient for large inputs.
Approach 2: Iterative Maximum Element Flip (Greedy) (O(n^2) time, O(1) space)
The efficient strategy treats pancake sorting like a selection sort using prefix reversals. Start from the largest unsorted value n. Find its index by iterating through the array. If the value is not already in its final position, perform two flips: first flip the prefix up to its index to bring it to the front, then flip the prefix of length n to move it to the end. Repeat the process for n-1, n-2, and so on until the array becomes sorted.
The key insight is that any element can be moved to the front with one flip and to its final position with another. Each iteration scans the remaining prefix and performs at most two reversals, leading to O(n) work per element and O(n^2) total time. The algorithm operates directly on the array with constant auxiliary space, aside from the list of flips returned.
This technique combines ideas from greedy algorithms and classic sorting strategies while operating directly on an array. Instead of swapping elements individually, you reposition the largest remaining value using prefix reversals.
Recommended for interviews: The iterative maximum-element flip approach. Interviewers expect the greedy insight: repeatedly place the largest remaining element using at most two flips. Explaining the brute-force thought process shows you understand the operation, but implementing the O(n^2) greedy strategy demonstrates stronger algorithmic reasoning.
Approach 1: Iterative Maximum Element Flip
This approach involves sorting the array by repeatedly moving the largest unsorted element to its correct position at the end. This is achieved by two flips: first flipping the array to get the largest element to the front, and then flipping up to the end of the unsorted part to push the largest element to the end.
def pancakeSort(arr):
res = []
cur_len = len(arr)
while cur_len > 1:
max_idx = arr.index(max(arr[:cur_len]))
if max_idx != cur_len - 1:
if max_idx != 0:
arr[:max_idx + 1] = arr[:max_idx + 1][::-1]
res.append(max_idx + 1)
arr[:cur_len] = arr[:cur_len][::-1]
res.append(cur_len)
cur_len -= 1
return res
arr = [3, 2, 4, 1]
print(pancakeSort(arr))import java.util.*;
public class PancakeSort {
public static List<Integer> pancakeSort(int[] arr) {
List<Integer> result = new ArrayList<>();
for (int i = arr.length - 1; i > 0; i--) {
int maxIndex = findMaxIndex(arr, i);
if (maxIndex != i) {
if (maxIndex != 0) {
reverse(arr, maxIndex);
result.add(maxIndex + 1);
}
reverse(arr, i);
result.add(i + 1);
}
}
return result;
}
private static void reverse(int[] arr, int k) {
int i = 0;
while (i < k) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
i++;
k--;
}
}
private static int findMaxIndex(int[] arr, int n) {
int maxIndex = 0;
for (int i = 0; i <= n; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
public static void main(String[] args) {
int[] arr = {3, 2, 4, 1};
List<Integer> flips = pancakeSort(arr);
flips.forEach(f -> System.out.print(f + " "));
}
}#include <vector>
#include <algorithm>
#include <iostream>
void reverse(std::vector<int>& arr, int k) {
std::reverse(arr.begin(), arr.begin() + k + 1);
}
int findMaxIndex(const std::vector<int>& arr, int n) {
return std::distance(arr.begin(), std::max_element(arr.begin(), arr.begin() + n + 1));
}
std::vector<int> pancakeSort(std::vector<int>& arr) {
int n = arr.size();
std::vector<int> result;
for (int i = n - 1; i > 0; --i) {
int maxIndex = findMaxIndex(arr, i);
if (maxIndex != i) {
if (maxIndex != 0) {
reverse(arr, maxIndex);
result.push_back(maxIndex + 1);
}
reverse(arr, i);
result.push_back(i + 1);
}
}
return result;
}
int main() {
std::vector<int> arr = {3, 2, 4, 1};
std::vector<int> flips = pancakeSort(arr);
for (int flip : flips) {
std::cout << flip << " ";
}
return 0;
}function pancakeSort(arr) {
let res = [];
for (let cur_len = arr.length; cur_len > 1; cur_len--) {
let max_idx = 0;
for (let i = 0; i < cur_len; i++) {
if (arr[i] > arr[max_idx]) max_idx = i;
}
if (max_idx !== cur_len - 1) {
if (max_idx !== 0) {
arr = arr.slice(0, max_idx + 1).reverse().concat(arr.slice(max_idx + 1));
res.push(max_idx + 1);
}
arr = arr.slice(0, cur_len).reverse().concat(arr.slice(cur_len));
res.push(cur_len);
}
}
return res;
}
const arr = [3, 2, 4, 1];
console.log(pancakeSort(arr));#include <stdio.h>
#include <stdlib.h>
void reverse(int* arr, int k) {
for (int i = 0, j = k; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int findMaxIndex(int* arr, int n) {
int maxIdx = 0;
for (int i = 1; i <= n; i++) {
if (arr[i] > arr[maxIdx]) {
maxIdx = i;
}
}
return maxIdx;
}
void pancakeSort(int* arr, int n) {
if (n <= 1) return;
for (int i = n - 1; i > 0; i--) {
int maxIndex = findMaxIndex(arr, i);
if (maxIndex != i) {
reverse(arr, maxIndex);
reverse(arr, i);
}
}
}
int main() {
int arr[] = {3, 2, 4, 1};
int n = sizeof(arr) / sizeof(arr[0]);
pancakeSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class PancakeSort {
public static IList<int> PancakeSortMethod(int[] arr) {
List<int> result = new List<int>();
for (int curLen = arr.Length; curLen > 1; curLen--) {
int maxIndex = FindMaxIndex(arr, curLen);
if (maxIndex != curLen - 1) {
if (maxIndex != 0) {
Reverse(arr, maxIndex);
result.Add(maxIndex + 1);
}
Reverse(arr, curLen - 1);
result.Add(curLen);
}
}
return result;
}
private static void Reverse(int[] arr, int k) {
int i = 0;
while (i < k) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
i++;
k--;
}
}
private static int FindMaxIndex(int[] arr, int n) {
int maxIndex = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
public static void Main() {
int[] arr = {3, 2, 4, 1};
IList<int> flips = PancakeSortMethod(arr);
foreach (int flip in flips) {
Console.Write(flip + " ");
}
}
}This Python solution uses list slicing to flip subarrays efficiently, and it appends the corresponding k-values to the result list as required.
Time Complexity: O(n^2), each flip and max computation in the array is O(n). Space Complexity: O(n) for storing results.
Approach 2: Default Approach
function pancakeSort(arr: number[]): number[] {
let ans = [];
for (let n = arr.length; n > 1; n--) {
let index = 0;
for (let i = 1; i < n; i++) {
if (arr[i] >= arr[index]) {
index = i;
}
}
if (index == n - 1) continue;
reverse(arr, index);
reverse(arr, n - 1);
ans.push(index + 1);
ans.push(n);
}
return ans;
}
function reverse(nums: Array<number>, end: number): void {
for (let i = 0, j = end; i < j; i++, j--) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}func pancakeSort(arr []int) []int {
var ans []int
n := len(arr)
reverse := func(j int) {
for i := 0; i < j; i, j = i+1, j-1 {
arr[i], arr[j] = arr[j], arr[i]
}
}
for i := n - 1; i > 0; i-- {
j := i
for ; j > 0 && arr[j] != i+1; j-- {
}
if j < i {
if j > 0 {
ans = append(ans, j+1)
reverse(j)
}
ans = append(ans, i+1)
reverse(i)
}
}
return ans
}impl Solution {
pub fn pancake_sort(mut arr: Vec<i32>) -> Vec<i32> {
let mut res = vec![];
for n in (1..arr.len()).rev() {
let mut max_idx = 0;
for idx in 0..=n {
if arr[max_idx] < arr[idx] {
max_idx = idx;
}
}
if max_idx != n {
if max_idx != 0 {
arr[..=max_idx].reverse();
res.push((max_idx as i32) + 1);
}
arr[..=n].reverse();
res.push((n as i32) + 1);
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Maximum Element Flip | Time Complexity: O(n^2), each flip and max computation in the array is O(n). Space Complexity: O(n) for storing results. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Flip Simulation | O(n^3) | O(1) | Understanding how prefix flips affect ordering; mainly conceptual or educational |
| Greedy Maximum Element Flip (Iterative) | O(n^2) | O(1) | Standard interview solution for pancake sorting; repeatedly places the largest remaining element |
| Recursive Pancake Placement | O(n^2) | O(n) recursion | Useful when expressing the same greedy logic recursively instead of iteratively |
Frequently asked questions
Is Pancake Sorting easy or hard?
Pancake Sorting is generally rated Medium difficulty. The core operation—reversing a prefix—is simple, but recognizing the greedy strategy of placing the maximum element with two flips requires some algorithmic insight. Once the pattern is clear, the implementation is straightforward.
Pancake Sorting Python/Java solution
In Python or Java, the solution iterates from n down to 1, finds the index of the current maximum element, and performs one or two prefix reversals using array slicing or manual swaps. Each flip reverses elements from index 0 to k. The resulting list of k values represents the sequence of pancake flips.
How to solve Pancake Sorting in O(n)?
An O(n) solution is not known for general pancake sorting with arbitrary permutations using only prefix reversals. The standard interview solution is O(n^2) because each step requires scanning for the maximum element and performing flips. Research variants of pancake sorting also typically remain quadratic.
What is the best approach for Pancake Sorting?
The standard solution uses a greedy strategy that repeatedly places the largest unsorted element at its final position. You first locate the maximum value in the current prefix, flip it to the front, then flip the prefix again to move it to the end. Each element requires at most two flips, resulting in O(n^2) time and O(1) auxiliary space.
Is Pancake Sorting asked at Google/Amazon/Meta?
Pancake Sorting is a well-known algorithmic puzzle that has appeared in technical interview practice sets and coding platforms like LeetCode. It tests understanding of greedy strategies, array manipulation, and in-place operations. Similar array transformation or custom sorting problems are common in interviews at large tech companies.
What data structure is used in Pancake Sorting?
The problem primarily uses an array with in-place prefix reversal operations. No advanced data structures are required. The algorithm relies on scanning the array to locate the maximum element and reversing segments of the array to reposition it.
What is the time complexity of Pancake Sorting?
The common greedy pancake sorting algorithm runs in O(n^2) time. Each iteration scans the array to find the maximum element in the unsorted prefix (O(n)) and performs up to two prefix reversals. Since this process repeats for n elements, the overall complexity becomes quadratic with constant extra space.