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 where 1 <= 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 to 0), 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.

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 index j. The function reverses the sub-array from the start up to the j-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 the i-th and j-th elements are swapped, incrementing i and decrementing j 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 the i-th largest value (which should be i+1 due to zero-indexing) by simply scanning the array from the start to the current position i. It uses a while loop for this, decrementing j until the value at arr[j] matches i+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 than 0, which means that the element is not at the start, it flips the sub-array up to j to bring the element to the front (a k value of j+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 to i (a k value of i+1 is appended to the result list).
The algorithm keeps track of all flips performed by appending the k values to the ans 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 Evaluator

Example 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 add k=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 add k=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 to 1, which gives us a total of n iterations.
Inside the outer loop, there is a while loop that searches for the position j of the i+1-th largest element. The while loop can iterate at most i 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 most 2n - 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: