#969

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Pancake Sorting

Sort an array using pancake flips, leveraging two-pointer scanning and invariant tracking to iteratively position the largest unsorted elements.

array two pointers greedy sorting

Problem Statement

Given an array of integers arr, your task is to sort the array by repeatedly performing pancake flips. Each flip reverses the order of the first k elements for some integer k.

A pancake flip consists of choosing an index k and reversing the sub-array arr[0..k-1]. For example, starting with arr = [3,2,1,4], performing a flip with k = 3 reverses the first three elements to produce arr = [1,2,3,4]. The goal is to return a sequence of flip positions that will sort the array.

Examples

Example 1

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

Output: [4,2,4,3]

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: []

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).

Solution Approach

Identify the largest unsorted element

Use a two-pointer scan from the unsorted portion of the array to locate the largest element. This ensures each flip moves the next maximum into place efficiently, respecting the problem's invariant tracking pattern.

Bring the largest element to the front if needed

If the largest element is not already at the start, perform a flip at its index to move it to the front. This guarantees subsequent flips correctly place elements without disrupting already sorted sections.

Flip the largest element into its correct position

Perform a flip at the current unsorted boundary index to move the largest element to its final sorted position. Repeat the process for remaining elements until the array is fully sorted, ensuring two-pointer invariant checks minimize unnecessary flips.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N^2)
Space	\mathcal{O}(N)

Time complexity is O(N^2) because for each element, locating it and performing up to two flips requires scanning up to N elements. Space complexity is O(N) to store the sequence of flips.

What Interviewers Usually Probe

Are you considering the two-pointer approach to locate the maximum efficiently?
Have you thought about minimizing flips by tracking sorted invariants?
Do you account for already positioned elements to avoid unnecessary flips?

Common Pitfalls or Variants

Common pitfalls

Flipping elements already in their correct positions, which increases flip count unnecessarily.
Failing to update the unsorted boundary, causing incorrect subsequent flips.
Ignoring the two-pointer scan and performing linear scans repeatedly, reducing efficiency.

Follow-up variants

Reverse only subarrays of fixed length, testing invariant management.
Sort arrays with duplicate elements, requiring additional checks for repeated values.
Minimize total number of flips for efficiency instead of just achieving a sorted array.

FAQ

What is the main pattern used in Pancake Sorting?

The key pattern is two-pointer scanning with invariant tracking to iteratively place the largest unsorted element.

How many flips are required at most for an array of length N?

At most 2*(N-1) flips may be needed, since each element may require one flip to bring it to the front and another to move it to its correct position.

Can Pancake Sorting handle already sorted arrays efficiently?

Yes, the algorithm can detect elements in their correct positions and skip flips, producing an empty sequence if the array is already sorted.

Why use two-pointer scanning instead of simple linear search?

Two-pointer scanning tracks the unsorted section and avoids rescanning sorted portions, maintaining the invariant and reducing unnecessary flips.

Are the flip positions in the output zero-based or one-based?

Flip positions are one-based indices, representing the number of elements to reverse from the start of the array.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        def reverse(arr, j):
            i = 0
            while i < j:
                arr[i], arr[j] = arr[j], arr[i]
                i, j = i + 1, j - 1

        n = len(arr)
        ans = []
        for i in range(n - 1, 0, -1):
            j = i
            while j > 0 and arr[j] != i + 1:
                j -= 1
            if j < i:
                if j > 0:
                    ans.append(j + 1)
                    reverse(arr, j)
                ans.append(i + 1)
                reverse(arr, i)
        return ans

Continue Practicing

#948 bag of tokens #881 boats to save people #870 advantage shuffle