Pancake Sorting

Problem Description

Given an array of integers arr, sort the array by performing a series of pancake flips. In one pancake flip, you choose an integer k where 1 <= k <= arr.length and reverse the sub-array arr[0...k-1]. 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.

Key Insights

• Each pancake flip can be visualized as reversing a prefix of the array.
• To sort the array, we can iteratively find the largest unsorted element and bring it to its correct position using at most two flips.
• The process involves finding the index of the maximum element, flipping it to the front, and then flipping it to its final position.
• Since the input is a permutation of integers from 1 to arr.length, the maximum value will always be present.

Space and Time Complexity

Time Complexity: O(n^2) - Each element can be moved to its sorted position using at most two flips, and finding the maximum takes O(n). Space Complexity: O(n) - We use an additional list to store the flip indices.

Solution

The algorithm works as follows:

1. Iterate through the array from the end to the beginning to find the maximum unsorted element.
2. If the maximum element is not already in its final position, perform a flip to bring it to the front, then another flip to move it to its correct position.
3. Record the values of k used for each flip in a list and return it at the end.

Code Solutions