LeetCode 969 - Pancake Sorting

The problem is asking us to sort an array of unique integers using only pancake flips. A pancake flip is defined as reversing a prefix of the array from index 0 to index k-1 for some integer k between 1 and the length of the array.

leetcodemediumarraytwo-pointersgreedysorting

LeetCode Problem 969

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting

Solution

Problem Understanding

The problem is asking us to sort an array of unique integers using only pancake flips. A pancake flip is defined as reversing a prefix of the array from index 0 to index k-1 for some integer k between 1 and the length of the array. The input is a permutation of integers from 1 to arr.length, which guarantees no duplicates, and the output must be a sequence of k values representing flips that will eventually sort the array in ascending order.

The key points to note are that each flip only affects a prefix, not the entire array, and the problem does not require the minimal number of flips. Any valid sequence of flips that sorts the array within 10 * arr.length flips is acceptable.

Important edge cases include arrays that are already sorted, arrays in reverse order, and arrays of length 1. The constraints (1 <= arr.length <= 100) are small enough that an algorithm with quadratic time complexity is acceptable.

Approaches

Brute Force

A brute force approach would attempt all possible sequences of flips to see which ones eventually sort the array. This could be done recursively by trying every possible k at each step until the array is sorted. While this guarantees a correct answer, the number of possible flip sequences grows factorially with the array length, making it infeasible even for small arrays.

Optimal Approach

The key insight for an efficient solution is to sort the array from largest to smallest, similar to selection sort, but using flips instead of swaps. For each value n from the largest down to 1, locate its current position in the array. If it is not already in its correct position, bring it to the front with a flip (if necessary), then flip it into its final position. By repeatedly moving the largest unsorted element to its correct position, we can sort the array efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Try all possible sequences of flips; infeasible for n > 10
Optimal O(n^2) O(1) Greedy approach, moves largest element to its correct position using at most 2 flips per element

Algorithm Walkthrough

  1. Initialize an empty list res to store the sequence of flips.
  2. Iterate from n = len(arr) down to 1. This represents the current largest element to place.
  3. Find the current index idx of n in the array. If idx + 1 == n, the element is already in the correct position, so skip it.
  4. If idx != 0, flip the sub-array from 0 to idx to bring the element n to the front. Append idx + 1 to res.
  5. Flip the sub-array from 0 to n-1 to move n to its final position. Append n to res.
  6. Repeat until all elements are placed in descending order, resulting in the array being sorted.

Why it works: The algorithm maintains the invariant that all elements larger than the current target are already in their correct position. By moving the largest remaining element to its correct position in at most two flips, the array gradually becomes sorted. Each step reduces the unsorted portion of the array by one element.

Python Solution

from typing import List

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        res = []
        n = len(arr)
        for target in range(n, 0, -1):
            idx = arr.index(target)
            if idx + 1 == target:
                continue
            if idx != 0:
                arr[:idx+1] = arr[:idx+1][::-1]
                res.append(idx + 1)
            arr[:target] = arr[:target][::-1]
            res.append(target)
        return res

The code iterates from the largest to the smallest element. For each element, it first checks if it is already in the correct position. If not, it flips the element to the front if needed, then flips it to its final position. The list res accumulates all k values used for the flips.

Go Solution

func pancakeSort(arr []int) []int {
    res := []int{}
    n := len(arr)
    
    for target := n; target >= 1; target-- {
        idx := 0
        for i, v := range arr {
            if v == target {
                idx = i
                break
            }
        }
        if idx+1 == target {
            continue
        }
        if idx != 0 {
            for i, j := 0, idx; i < j; i, j = i+1, j-1 {
                arr[i], arr[j] = arr[j], arr[i]
            }
            res = append(res, idx+1)
        }
        for i, j := 0, target-1; i < j; i, j = i+1, j-1 {
            arr[i], arr[j] = arr[j], arr[i]
        }
        res = append(res, target)
    }
    
    return res
}

In Go, we manually reverse slices using a two-pointer swap approach because Go does not support slicing assignment with reverse. The logic mirrors the Python version closely, handling the search for the target and the flips.

Worked Examples

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

Step Action Array res
1 target = 4, idx = 2 [3,2,4,1] flip idx+1 = 3 → [4,2,3,1]
2 flip target = 4 → [1,3,2,4] [1,3,2,4] [3,4]
3 target = 3, idx = 1 [1,3,2,4] flip idx+1 = 2 → [3,1,2,4]
4 flip target = 3 → [2,1,3,4] [2,1,3,4] [3,4,2,3]
5 target = 2, idx = 0 [2,1,3,4] flip target = 2 → [1,2,3,4]

Sorted array obtained.

Example 2: arr = [1,2,3]

Already sorted; no flips required, result is [].

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Each iteration searches for the target element and may perform up to two flips, each O(n)
Space O(1) Flips are done in-place, only the result list stores flips

Even though the worst-case time is quadratic, the problem constraints (n <= 100) make this feasible. Space is minimal because we only use the result array.

Test Cases

# Basic examples
assert Solution().pancakeSort([3,2,4,1]) == [4,2,4,3] or Solution().pancakeSort([3,2,4,1]) != []  # general valid flips
assert Solution().pancakeSort([1,2,3]) == []  # already sorted

# Edge cases
assert Solution().pancakeSort([1]) == []  # single element
assert Solution().pancakeSort([2,1]) == [2]  # two elements reversed
assert Solution().pancakeSort([3,1,2]) != []  # small unsorted

# Reverse sorted
assert Solution().pancakeSort([5,4,3,2,1]) != []  # maximum flips needed
Test Why
[3,2,4,1] Typical unsorted array
[1,2,3] Already sorted array
[1] Single element edge case
[2,1] Minimal unsorted array
[3,1,2] Small permutation
[5,4,3,2,1] Worst-case reverse order

Edge Cases

A single-element array [1] requires no flips. The algorithm correctly skips all iterations.

A two-element reversed array [2,1] tests minimal flips. The first flip moves 2 to the front (trivial), then another flip places it correctly.

A reverse-sorted array [n,...,1] tests the algorithm’s efficiency under maximal flips. Each element requires up to two flips, showing that the solution performs at most 2*n flips, within the problem’s allowed limit.

This solution correctly handles all edge cases, guaranteeing the array is sorted using only valid pancake flips.