{x}
blog image

Pancake Sorting

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:

  • Choose an integer k where 1 <= k <= arr.length.
  • Reverse the sub-array 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 <= 100
  • 1 <= arr[i] <= arr.length
  • All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

Pancake Sorting Solution Explanation

The Pancake Sorting problem asks to sort an array using only pancake flips. A pancake flip reverses a prefix of the array. The goal is to find the sequence of flip positions (k values) that sorts the array.

Approach

The solution employs a greedy approach. We iterate through the array from right to left. In each iteration, we find the largest unsorted element and move it to its correct sorted position at the end of the unsorted portion. This is done using two flips:

  1. Find the index: Locate the index j of the largest unsorted element (target element).
  2. First flip: If j > 0, flip the prefix up to index j to bring the target element to the beginning of the array.
  3. Second flip: Flip the prefix up to the current index i to move the target element to its correct sorted position.

This process is repeated until the entire array is sorted.

Time and Space Complexity Analysis

  • Time Complexity: O(n^2). The outer loop iterates n-1 times. The inner loop (finding the index j) has a worst-case complexity of O(n). The flips are O(n) operations as well. Therefore, the overall time complexity is dominated by the nested loop, resulting in O(n^2).

  • Space Complexity: O(n) in the worst case. This is due to storing the ans array (list of k values) which can have a maximum size of 2n-1 in the worst-case scenarios (although generally it's less than that). The space used by the array arr itself is not considered in the auxiliary space complexity.

Code Explanation (Python3 as Example)

The Python3 code effectively implements the above approach.

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        def reverse(arr, j):  # Helper function to reverse a subarray
            i = 0
            while i < j:
                arr[i], arr[j] = arr[j], arr[i]
                i, j = i + 1, j - 1
 
        n = len(arr)
        ans = [] #stores the k values for the flips
        for i in range(n - 1, 0, -1): #iterate from the end
            j = i #start searching from current index
            while j > 0 and arr[j] != i + 1: #find the index of the largest unsorted element
                j -= 1
            if j < i:  #if the element is not in the correct position
                if j > 0: #first flip only needed if the element is not already at index 0
                    ans.append(j + 1)
                    reverse(arr, j)  
                ans.append(i + 1)  #append the k value for the second flip
                reverse(arr, i)  #perform the second flip
        return ans

The reverse helper function efficiently reverses a subarray in place. The main loop iterates, finds the largest unsorted element, and performs the necessary flips, appending the k values to the ans list. The other language implementations follow a very similar structure and logic.