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:

1. Choose an integer k where 1 <= k <= arr.length.
2. 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:

Input: arr = [3,2,4,1] Output: [4,2,4,3]

Explain the algorithm and analyze the time and space complexity.

def pancakeSort(arr):
    flips = []
    n = len(arr)

    for i in range(n, 0, -1):
        # Find the index of the maximum element in the unsorted part of the array
        max_index = arr.index(i)

        # If the maximum element is not already in its correct position
        if max_index != i - 1:
            # Flip the array to bring the maximum element to the front
            if max_index != 0:
                arr[:max_index + 1] = arr[:max_index + 1][::-1]
                flips.append(max_index + 1)

            # Flip the array to bring the maximum element to its correct position
            arr[:i] = arr[:i][::-1]
            flips.append(i)

    return flips

# Example usage
arr = [3, 2, 4, 1]
result = pancakeSort(arr)
print(f"Pancake flips: {result}")

Explanation:

The pancakeSort function takes an array arr as input and returns a list of k values representing the pancake flips needed to sort the array.

1. Iterate Through Unsorted Parts: The code iterates from n down to 1 (inclusive), where n is the length of the array. In each iteration, the goal is to place the number i at its correct index (i-1).
2. Find Maximum Element: max_index = arr.index(i) finds the index of the element with value i in the current state of the array.
3. Flip to Front (if needed): If max_index is not 0, it means the element i is not at the beginning of the array. In this case, the code performs a pancake flip to bring it to the front: arr[:max_index + 1] = arr[:max_index + 1][::-1]. The value max_index + 1 is appended to the flips list.
4. Flip to Correct Position: After the previous step, the maximum element i is at the front of the array. Then, the code performs another flip to bring this element to its correct sorted position at the end of the sorted portion of the array: arr[:i] = arr[:i][::-1]. The value i is appended to the flips list.
5. Return Flips: The function returns the flips list containing the sequence of pancake flips.

Big O Time Complexity:

• The outer loop iterates n times (from n down to 1).
• Inside the loop, arr.index(i) takes O(n) time in the worst case because it has to potentially scan the entire array to find the index of element i.
• The slicing and reversing arr[:max_index + 1][::-1] and arr[:i][::-1] take O(k) time where k is the length of the slice, in our case it's O(n).

Therefore, the overall time complexity is O(n * (n + n)) which simplifies to O(n^2).

Big O Space Complexity:

• The flips list stores at most 3n elements, because in each iteration of the outer loop, we add at most two elements to the flips list. Therefore, the space complexity is O(n).
• The in-place reversal operations don't require significant extra space.
• Therefore, the overall space complexity is O(n).