We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Pancake Sorting

Number: 1009

Difficulty: Medium

Paid? No

Companies: Microsoft, Oracle, Amazon, Block

Problem Description

Given an array of integers that is a permutation of [1, 2, …, n], sort it using only pancake flips. A pancake flip reverses the sub-array from index 0 up to a chosen index k-1. Return a sequence of k values such that performing flips in that order sorts the array. An answer using at most 10 * arr.length flips is accepted.

Key Insights

  • Identify the largest unsorted element and place it in its correct position.
  • Two flips are sufficient for each element: one flip to bring the maximum element to the front and another to move it to its correct position.
  • Iteratively reduce the unsorted portion of the array.
  • Optimally, if the element is already in the correct position, no flip is needed.
  • Handle the already sorted case gracefully.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario, due to scanning for maximums and performing flips. Space Complexity: O(1) extra space (not including output), as operations are done in place.

Solution

The solution employs a greedy approach. For each iteration, we:

  1. Find the index of the maximum element in the unsorted portion (from index 0 to currSize-1).
  2. If this maximum is not already at the end:
    • If the maximum is not at the beginning, perform a flip to bring it to the front.
    • Then, perform a flip of the entire unsorted array to move the maximum to its correct position.
  3. Continue this process until the entire array is sorted.

Code Solutions

# Function to perform pancake sort
def pancakeSort(arr):
    result = []  # List to store the sequence of flips
    n = len(arr)
    
    # Process each unsorted sub-array from the end of the array
    for curr_size in range(n, 1, -1):
        # Find index of the maximum element in arr[0:curr_size]
        max_index = arr.index(max(arr[:curr_size]))
        
        # Only perform flips if the max element isn't already in place
        if max_index != curr_size - 1:
            # Flip to bring max element to the front if needed
            if max_index != 0:
                result.append(max_index + 1)
                arr[:max_index+1] = arr[:max_index+1][::-1]
            # Flip to move the max element to its correct position
            result.append(curr_size)
            arr[:curr_size] = arr[:curr_size][::-1]
            
    return result

# Example usage:
arr = [3,2,4,1]
print(pancakeSort(arr))  # Expected output: A valid sequence like [4,2,4,3]
← Back to All Questions