Pancake Sorting Algorithm

LeetCode Problem 969, "Pancake Sorting," presents an interesting real-world challenge: Suppose there are n pancakes of varying sizes on a plate. How can you use a spatula to flip them multiple times until they are ordered by size (smallest on top, largest at the bottom)?

Consider the constraints of flipping pancakes with a spatula: each time you can only flip the top several pancakes:

The core question is: How can we derive an algorithm to produce a sequence of flips that sorts the pancake stack?

First, we abstract the problem by representing the pancake stack with an array:

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.

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.

How do we solve this? Similar to the approach in the previous article Recursively Reversing Part of a Linked List, this problem requires recursive thinking.

I. Approach Analysis

Why does this problem have a recursive nature? For example, suppose we need to implement a function such as:

// cakes is a pile of pancakes, the function will sort the first n pancakes
void sort(int[] cakes, int n);

// cakes is a pile of pancakes, the function will sort the first n pancakes
void sort(int cakes[], int n);

# cakes is a pile of pancakes, the function will sort the first n pancakes
def sort(cakes: List[int], n: int):

// cakes is a pile of pancakes, the function will sort the first n pancakes
func sort(cakes []int, n int) {}

// cakes is a pile of pancakes, the function will sort the first n pancakes
var sort = function(cakes, n) {
};

If we find the largest pancake among the first n pancakes and then flip it to the bottom:

The size of the original problem can be reduced, and we can recursively call pancakeSort(A, n-1):

Next, how do we sort the remaining n - 1 pancakes? We still find the largest pancake among them, move it to the bottom, and then recursively call pancakeSort(A, n-1-1)...

You see, this is the nature of recursion. To summarize the approach:

1. Find the largest pancake among the n pancakes.
2. Move this largest pancake to the bottom.
3. Recursively call pancakeSort(A, n - 1).

Base case: When n == 1, sorting one pancake requires no flipping.

So, the last question remains: How do we move a specific pancake to the end?

It's quite simple. For example, if the 3rd pancake is the largest and we want to move it to the end (i.e., the nth position), we can do the following:

1. Flip the first 3 pancakes with a spatula, so the largest pancake moves to the top.
2. Flip all the first n pancakes, so the largest pancake moves to the nth position, which is the last one.

Once you understand these two steps, you can basically write the solution. However, the problem requires us to write out the specific sequence of flip operations, which is also simple. Just record each flip operation.

II. Code Implementation

You just need to implement the above approach in code. The only thing to note is that array indices start from 0, but the results we return should be counted from 1.

class Solution {
    // record the sequence of flip operations
    LinkedList<Integer> res = new LinkedList<>();

    public List<Integer> pancakeSort(int[] cakes) {
        sort(cakes, cakes.length);
        return res;
    }

    void sort(int[] cakes, int n) {
        // base case
        if (n == 1) return;
        
        // find the index of the largest cake
        int maxCake = 0;
        int maxCakeIndex = 0;
        for (int i = 0; i < n; i++)
            if (cakes[i] > maxCake) {
                maxCakeIndex = i;
                maxCake = cakes[i];
            }
        
        // first flip, flip the largest cake to the top
        reverse(cakes, 0, maxCakeIndex);
        res.add(maxCakeIndex + 1);
        // second flip, flip the largest cake to the bottom
        reverse(cakes, 0, n - 1);
        res.add(n);


        // recursive call
        sort(cakes, n - 1);

    }

    void reverse(int[] arr, int i, int j) {
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
}

class Solution {
public:
    // record the sequence of reversal operations
    vector<int> res;

    vector<int> pancakeSort(vector<int>& cakes) {
        sort(cakes, cakes.size());
        return res;
    }

    void sort(vector<int>& cakes, int n) {
        // base case
        if (n == 1) return;

        // find the index of the largest cake
        int maxCake = 0;
        int maxCakeIndex = 0;
        for (int i = 0; i < n; i++)
            if (cakes[i] > maxCake) {
                maxCakeIndex = i;
                maxCake = cakes[i];
            }

        // first reversal, flip the largest cake to the top
        reverse(cakes, 0, maxCakeIndex);
        res.push_back(maxCakeIndex + 1);
        // second reversal, flip the largest cake to the bottom
        reverse(cakes, 0, n - 1);
        res.push_back(n);

        // recursive call
        sort(cakes, n - 1);
    }

    void reverse(vector<int>& arr, int i, int j) {
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
};

from typing import List

class Solution:
    def pancakeSort(self, cakes: List[int]) -> List[int]:
        # record the sequence of reversal operations
        self.res = []
        self.sort(cakes, len(cakes))
        return self.res
    
    def sort(self, cakes: List[int], n: int) -> None:
        # base case
        if n == 1:
            return
        # find the index of the largest cake
        max_cake = 0
        max_cake_index = 0
        for i in range(n):
            if cakes[i] > max_cake:
                max_cake_index = i
                max_cake = cakes[i]
        # first reversal, flip the largest cake to the top
        self.reverse(cakes, 0, max_cake_index)
        self.res.append(max_cake_index + 1)
        # second reversal, flip the largest cake to the bottom
        self.reverse(cakes, 0, n - 1)
        self.res.append(n)

        # recursive call
        self.sort(cakes, n - 1)
        
    def reverse(self, arr: List[int], i: int, j: int) -> None:
        while i < j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1

func pancakeSort(cakes []int) []int {
    res := []int{}
    sort(cakes, len(cakes), &res)
    return res
}

func sort(cakes []int, n int, res *[]int) {
    // base case
    if n == 1 {
        return
    }

    // find the index of the largest cake
    maxCake := 0
    maxCakeIndex := 0
    for i := 0; i < n; i++ {
        if cakes[i] > maxCake {
            maxCakeIndex = i
            maxCake = cakes[i]
        }
    }

    // first flip, flip the largest cake to the top
    reverse(cakes, 0, maxCakeIndex)
    *res = append(*res, maxCakeIndex+1)
    
    // second flip, flip the largest cake to the bottom
    reverse(cakes, 0, n-1)
    *res = append(*res, n)

    // recursive call
    sort(cakes, n-1, res)
}

func reverse(arr []int, i int, j int) {
    for i < j {
        arr[i], arr[j] = arr[j], arr[i]
        i++
        j--
    }
}

var pancakeSort = function(cakes) {
    // record the sequence of flip operations
    const res = [];

    const sort = function(cakes, n) {
        // base case
        if (n == 1) return;
        
        // find the index of the largest pancake
        let maxCake = 0;
        let maxCakeIndex = 0;
        for (let i = 0; i < n; i++)
            if (cakes[i] > maxCake) {
                maxCakeIndex = i;
                maxCake = cakes[i];
            }
        
        // first flip, flip the largest pancake to the top
        reverse(cakes, 0, maxCakeIndex);
        res.push(maxCakeIndex + 1);
        // second flip, flip the largest pancake to the bottom
        reverse(cakes, 0, n - 1);
        res.push(n);

        // recursive call
        sort(cakes, n - 1);
    };

    const reverse = function(arr, i, j) {
        while (i < j) {
            var temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    };

    sort(cakes, cakes.length);
    return res;
};

With the detailed explanation above, this code should be quite clear now.

The time complexity of the algorithm is easy to calculate. Since the number of recursive calls is n and each recursive call involves a for loop, the time complexity is O(n). Therefore, the overall complexity is O(n^2).

Finally, let's ponder a question: Following our approach, the length of the operation sequence should be 2(n - 1). This is because each recursive call performs 2 flips and records the operations, and there are n levels of recursion. However, due to the base case returning the result directly without flipping, the final operation sequence length should be a fixed 2(n - 1).

Clearly, this result is not optimal (the shortest). For example, with a stack of pancakes [3,2,4,1], our algorithm yields the flip sequence [3,4,2,3,1,2], but the quickest flip method should be [2,3,4]:

Initial state: [3,2,4,1]
Flip first 2: [2,3,4,1]
Flip first 3: [4,3,2,1]
Flip first 4: [1,2,3,4]

If you were asked to design an algorithm to compute the shortest operation sequence for sorting pancakes, how would you approach it? Or, more generally, what is the core idea for solving such optimization problems, and what algorithmic techniques might be essential?

Feel free to share your thoughts.