969. Pancake Sorting
Problem Description
The problem provides us with an array of integers arr
. We are tasked with sorting this array but not through conventional means. The only operation we can perform is what's termed as a "pancake flip." A pancake flip involves the following steps:
- Select an integer
k
where1 <= k <= arr.length
. - Reverse the sub-array
arr[0...k-1]
, which is zero-indexed.
Our goal is to sort the entire array by performing a series of these pancake flips. To illustrate, if our array is [3,2,1,4]
and we perform a pancake flip with k = 3
, we reverse the sub-array [3,2,1]
, turning the array into [1,2,3,4]
. The desired output is not the sorted array itself but rather a sequence of k
values for each flip performed to sort the array. Importantly, any sequence that sorts the array within 10 * arr.length
flips is considered correct.
Intuition
The key to solving this problem lies in reducing it to smaller sub-problems. We can sort the array one number at a time, specifically by moving the largest number not yet in place to its final position through a sequence of at most two flips:
- First, flip the largest number to the beginning of the array (unless it's already there).
- Then flip it again to its final destination in the sorted array.
By repeating this process for the largest number down to the smallest, we can sort the entire array.
Now let's dive into the solution intuition:
- We iterate from the end of the array to the beginning (
i = n-1
to0
), as the end of the array represents where the next largest number should go. - We then find the index
j
where the next largest number is (i+1
indicates the number we're looking for each iteration). - If the largest number is not already in position
i
(j < i
), we perform up to two flips:- The first flip moves the largest number to the start of the array (
j = 0
). This is only needed if the number is not already at the start (j > 0
). - The second flip moves the number from the start to its correct position
i
.
- The first flip moves the largest number to the start of the array (
We keep a list of k
values for each flip performed and return it as the result.
Learn more about Greedy, Two Pointers and Sorting patterns.
Solution Approach
The solution provided uses a simple greedy algorithm to sort the array using the constraints of pancake flips.
To understand the implementation, let's walk through the algorithm and data structures used:
-
A helper function named
reverse
is defined which takes the array and an indexj
. The function reverses the sub-array from the start up to thej-th
element (i.e.,arr[0...j]
). Simple swapping within the array is used for this operation. This is done using a while loop, where thei-th
andj-th
elements are swapped, incrementingi
and decrementingj
until they meet or cross. No additional data structures are needed here; in-place swapping is sufficient. -
The main function,
pancakeSort
, iterates over the elements of the array in reverse order, from the last element down to the second one (as the first one will be naturally sorted if all others are). Here,n
is the length of the array. -
In each iteration, it finds the correct position
j
for thei-th
largest value (which should bei+1
due to zero-indexing) by simply scanning the array from the start to the current positioni
. It uses awhile
loop for this, decrementingj
until the value atarr[j]
matchesi+1
. -
Once the position of the unsorted largest element is found, if it's not already at its correct position, we proceed with up to two flips:
- If
j
is greater than0
, which means that the element is not at the start, it flips the sub-array up toj
to bring the element to the front (ak
value ofj+1
is appended to the result list). - The next flip brings the element from the start to its designated position
i
by reversing the sub-array from the start up toi
(ak
value ofi+1
is appended to the result list).
- If
-
The algorithm keeps track of all flips performed by appending the
k
values to theans
list, which is the final result of the function.
The reasoning behind this approach is that each iteration ensures the next largest value is placed at its final position, reducing the problem's size by one each time. Since the relative order of the previous flips is not disrupted by further flips (they only affect elements before the largest placed element), the array is sorted correctly at the end of the algorithm.
This approach does not require any advanced data structures. It leverages the fact that we can greedily place each largest unsorted value in its final place step by step, making it a simple yet powerful solution given the unique constraints of the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example array [3,1,2]
to illustrate the solution approach detailed above.
- Our goal is to sort the array
[3,1,2]
using pancake flips. - We start by looking for the position of the largest number that is not yet in its correct place. Since the array is of length 3, we begin with the number 3, which is also the largest.
- We find that the largest number, 3, is already in the first position. This means we do not need the first flip; we can directly proceed to the second flip.
- We perform the second flip at the third position to move the number 3 to the end of the array. We reverse the sub-array
[3,1,2]
, resulting in[2,1,3]
. We addk=3
to our sequence of flips, as we flipped the first three elements. - Now, the largest number is in the correct position, and we ignore it in subsequent steps. We are left with considering the sub-array
[2,1]
. - Next, we move to the second largest number, which is 2. This is not in the correct position, so we find it at position 0.
- We perform our first flip to bring the number 2 to the beginning of the array (though it's already there, so this flip is redundant and can be skipped).
- We then perform the second flip at the second position to move the number 2 to its correct location before the number 3. We reverse the sub-array
[2,1]
, turning it into[1,2]
. We addk=2
to our sequence of flips, as we flipped the first two elements. - Now, our array is fully sorted as
[1,2,3]
, and our sequence of flips that were required is[3,2]
.
Thus, the sequence [3,2]
represents the series of k
values for each flip we performed to sort the array [3,1,2]
. In practice, we could have avoided the redundant flip when the largest number was already at the beginning, but this walkthrough includes it for illustration purposes.
Solution Implementation
1from typing import List
2
3class Solution:
4 def pancakeSort(self, arr: List[int]) -> List[int]:
5 # Helper function to reverse the array from start to index 'k'.
6 def flip(arr, k):
7 start = 0
8 while start < k:
9 # Swap values
10 arr[start], arr[k] = arr[k], arr[start]
11 start += 1
12 k -= 1
13
14 n = len(arr)
15 flips = [] # To store the sequence of flips
16
17 # Start sorting from the end of the array
18 for target_index in range(n - 1, 0, -1):
19 # Find the index of the next largest element to sort
20 max_index = arr.index(target_index + 1)
21
22 # If the largest element is not already in place
23 if max_index != target_index:
24 # Bring the largest element to the start if it's not already there
25 if max_index > 0:
26 flips.append(max_index + 1)
27 flip(arr, max_index)
28 # Now flip the largest element to its correct target index
29 flips.append(target_index + 1)
30 flip(arr, target_index)
31
32 return flips
33
1import java.util.List;
2import java.util.ArrayList;
3
4class Solution {
5 // Method to sort the array using pancake sort
6 public List<Integer> pancakeSort(int[] arr) {
7 int length = arr.length; // The length of the array
8 List<Integer> ans = new ArrayList<>(); // The list to store the flips performed
9
10 // Start from the end of the array and move towards the start
11 for (int i = length - 1; i > 0; --i) {
12 // Find the index of the next largest value expected at 'i'
13 int maxIndex = i;
14 while (maxIndex > 0 && arr[maxIndex] != i + 1) {
15 --maxIndex;
16 }
17
18 // Perform the necessary flips
19 if (maxIndex < i) {
20 // Flip the sub-array if the max index is not at the beginning
21 if (maxIndex > 0) {
22 ans.add(maxIndex + 1); // Add the flip position to the answer list
23 reverse(arr, maxIndex); // Flip the sub-array from 0 to maxIndex
24 }
25 ans.add(i + 1); // Flip the sub-array from 0 to i
26 reverse(arr, i); // Performed to move the max element to the correct position
27 }
28 }
29 return ans; // Return the list of flip positions
30 }
31
32 // Method to reverse the elements in the sub-array from index 0 to index j
33 private void reverse(int[] arr, int j) {
34 for (int i = 0; i < j; i++, j--) {
35 int temp = arr[i]; // Temporary variable to hold the current element
36 arr[i] = arr[j]; // Swap the elements
37 arr[j] = temp;
38 }
39 }
40}
41
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 std::vector<int> pancakeSort(std::vector<int>& arr) {
7 int n = arr.size();
8 std::vector<int> sorted_operations;
9
10 // We iterate over each element in the array starting from the end
11 for (int target_position = n - 1; target_position > 0; --target_position) {
12 int current_index = target_position;
13
14 // Find the index of the next largest element which should be at target_position
15 for (; current_index > 0 && arr[current_index] != target_position + 1; --current_index);
16
17 // If the element is already in the right place, skip it
18 if (current_index == target_position) continue;
19
20 // If the element is not at the beginning, flip the subarray so that the element
21 // is at the beginning
22 if (current_index > 0) {
23 sorted_operations.push_back(current_index + 1); // We add +1 because indices are 1-based in pancake sort
24 std::reverse(arr.begin(), arr.begin() + current_index + 1); // Perform the flip operation
25 }
26
27 // Next, flip the subarray to move the element from the beginning to its target position
28 sorted_operations.push_back(target_position + 1);
29 std::reverse(arr.begin(), arr.begin() + target_position + 1);
30 }
31
32 // Return the sequence of flips performed to sort the array
33 return sorted_operations;
34 }
35};
36
1// Function to sort an array using pancake sort algorithm.
2// The main idea is to do a series of pancake flips (reversing sub-arrays) to sort the array.
3function pancakeSort(arr: number[]): number[] {
4 let output = []; // This will store our sequence of flips.
5
6 // Iterate over the array from the last element down to the second one.
7 for (let currentSize = arr.length; currentSize > 1; currentSize--) {
8 let maxIndex = 0;
9
10 // Find the index of the largest element in the unsorted part of the array.
11 for (let i = 1; i < currentSize; i++) {
12 if (arr[i] >= arr[maxIndex]) {
13 maxIndex = i;
14 }
15 }
16
17 // If the largest element is already at its correct position, continue.
18 if (maxIndex == currentSize - 1) continue;
19
20 // Otherwise, flip the array at maxIndex and at currentSize - 1 to move
21 // the largest element to its correct position.
22 // Add the flip operations (+1 because operations are 1-based in pancakesort problem).
23 if (maxIndex > 0) {
24 reverse(arr, maxIndex);
25 output.push(maxIndex + 1);
26 }
27 reverse(arr, currentSize - 1);
28 output.push(currentSize);
29 }
30
31 return output; // Return the sequence of flips.
32}
33
34// Function to reverse the elements in the array from index 0 to end.
35function reverse(nums: number[], end: number): void {
36 let start = 0; // Start of the sub-array to reverse.
37
38 // Swap positions starting from the ends towards the center.
39 while (start < end) {
40 [nums[start], nums[end]] = [nums[end], nums[start]]; // Perform the swap.
41 start++;
42 end--;
43 }
44}
45
Time and Space Complexity
The provided code achieves the goal of sorting a list through a series of pancake flips, which are represented as reversals of prefixes of the array. To analyze the time and space complexity, we need to consider both the number of reversals performed and the impact of each reversal on time and space.
Time Complexity:
- The outer loop runs from
n - 1
down to1
, which gives us a total ofn
iterations. - Inside the outer loop, there is a while loop that searches for the position
j
of thei+1-th
largest element. The while loop can iterate at mosti
times in the worst case, which is when the largest element is at the beginning of the array. - Two reversals can occur in each iteration of the outer loop; one if the largest element is not already in the right place, and another reversal puts the largest element at the end of the array.
This yields a total of at most 2n
reversals (each involving at most n
elements to be swapped) across all iterations of the outer loop. Consequently, the worst-case time complexity is O(n^2)
because each of the 2n
reversals takes up to O(n)
time.
Space Complexity:
The space complexity of the code consists of the space used by the input array and the additional space used to store the answer list that keeps track of the flips.
- No additional data structures that depend on the size of the input are allocated; the reversals are performed in place.
- The
ans
list will contain at most2n - 2
elements because, in the worst case, two flips are performed for each element except for the last one.
Therefore, the space complexity is O(n)
for the ans
list, in addition to O(1)
auxiliary space for the variables used, which results in total space complexity of O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced