Scale Engineer

Pancake Sorting

Med
#0923Time: O(N * N!). There are `N!` possible states (permutations). For each state, we might perform `N-1` flips. Each flip and the subsequent state creation takes `O(N)` time.Space: O(N * N!). In the worst case, we might need to store a significant fraction of all `N!` permutations in the queue and visited set. Each permutation requires `O(N)` space.1 company
Patterns
Two PointersGreedy
Algorithms
Sorting
Data structures
Array
Companies
Block

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach seeks the optimal solution (the shortest sequence of flips) by treating the problem as a shortest path search on a state-space graph. The states are all possible permutations of the input array, and an edge exists between two states if one can be transformed into the other by a single pancake flip. Breadth-First Search (BFS) is the natural algorithm for finding the shortest path in an unweighted graph like this.

Algorithm

  • Model the problem as a shortest path problem on a graph where nodes are array permutations and edges are pancake flips.
  • Use Breadth-First Search (BFS) to explore the state space, starting from the initial array configuration.
  • Maintain a queue of states (current_array, path_of_flips) and a set of visited permutations to avoid cycles.
  • Start BFS with the initial arr and an empty path.
  • In each step, dequeue a state. If the array is sorted, return the path.
  • Otherwise, generate all possible next states by applying flips with k from 2 to n.
  • For each new, unvisited state, add it to the queue and the visited set with the updated path.

Walkthrough

The core of this method is a systematic exploration of all possible sequences of flips, level by level. We start with the initial array as the root of our search.

We use a queue to manage the states to visit, where each state consists of a permutation of the array and the list of k-values (flips) used to reach it. To prevent getting into infinite loops and re-computing results for the same array configuration, we use a Set to keep track of all permutations we have already visited.

The BFS algorithm proceeds as follows: dequeue a state, check if it's the sorted state. If it is, we've found the shortest path, and we return the sequence of flips. If not, we generate all valid subsequent states by applying every possible pancake flip (for k from 2 to n). For each newly generated permutation that has not been visited, we add it to our queue and visited set, along with the path extended by the new flip's k-value.

While this approach guarantees an optimal solution, the number of possible permutations is n!, which grows astronomically. For n=10, n! is over 3.6 million, and for n=100, it's computationally impossible to explore. Therefore, this approach is purely theoretical for the given problem constraints.

Note: A full code implementation is omitted due to its impracticality and high complexity for the given constraints.

Complexity

Time

O(N * N!). There are `N!` possible states (permutations). For each state, we might perform `N-1` flips. Each flip and the subsequent state creation takes `O(N)` time.

Space

O(N * N!). In the worst case, we might need to store a significant fraction of all `N!` permutations in the queue and visited set. Each permutation requires `O(N)` space.

Trade-offs

Pros

  • Guarantees finding the optimal solution, i.e., the minimum number of flips required to sort the array.

Cons

  • Extremely high time and space complexity, making it infeasible for the given constraints (n <= 100).

  • Complex to implement, especially handling array/list states in a hash set.

Solutions

class Solution { public List < Integer > pancakeSort ( int [] arr ) { int n = arr . length ; List < Integer > ans = new ArrayList <>(); for ( int i = n - 1 ; i > 0 ; -- i ) { int j = i ; for (; j > 0 && arr [ j ] != i + 1 ; -- j ) ; if ( j < i ) { if ( j > 0 ) { ans . add ( j + 1 ); reverse ( arr , j ); } ans . add ( i + 1 ); reverse ( arr , i ); } } return ans ; } private void reverse ( int [] arr , int j ) { for ( int i = 0 ; i < j ; ++ i , -- j ) { int t = arr [ i ]; arr [ i ] = arr [ j ]; arr [ j ] = t ; } } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem