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:
k where 1 <= k <= arr.length.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.lengtharr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).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.
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.
The C solution identifies the maximum element in the unsorted portion of the array and brings it to the 0th index if it isn't already there. Then, it reverses the entire array up to the current unsorted subarray length to place the maximum at its sorted position. This process is repeated for the rest of the elements.
Time Complexity: O(n^2) due to nested loops finding the maximum index and reversing. Space Complexity: O(1) due to in-place operations.
| Approach | Complexity |
|---|---|
| Iterative Maximum Element Flip | Time Complexity: O(n^2) due to nested loops finding the maximum index and reversing. Space Complexity: O(1) due to in-place operations. |
| Default Approach | — |
| 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 |
Pancake Sorting | LeetCode 969 | C++, Java, Python • Knowledge Center • 15,528 views views
Watch 9 more video solutions →Practice Pancake Sorting with our built-in code editor and test cases.
Practice on FleetCode