# Pancake Sorting
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/pancake-sorting)
Canonical: https://scaleengineer.com/dsa/problems/pancake-sorting
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Block](https://scaleengineer.com/companies/block)
---
## Problem
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
## Brute-Force with Breadth-First Search (BFS)
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.
**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.
**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.
### Explanation
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.*
### 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.

## Greedy Strategy (Selection Sort-like)
A highly effective and efficient approach is a greedy strategy that works backward from the largest element. This method is analogous to Selection Sort. In each step, it identifies the largest unsorted element and places it in its correct final position using at most two pancake flips. This process is repeated for the next largest element until the entire array is sorted.
**Time:** O(N^2). The main loop runs `N-1` times. Inside the loop, finding the index takes `O(N)` time, and each of the two flips also takes `O(N)` time. This results in a total time complexity of `O(N * N) = O(N^2)`. · **Space:** O(N). The space is dominated by the `result` list, which can store up to `2*(N-1)` integers. Auxiliary space is O(1).
**Pros:** Simple to understand and implement.; Efficient with a time complexity of O(N^2), which is fast enough for the given constraints.; Guaranteed to sort the array within the required number of flips (at most 2*(N-1) flips).
**Cons:** Does not find the optimal (shortest) sequence of flips.
### Explanation
The algorithm iterates from `n` down to 1, where `n` is the length of the array. For each value `x` in this sequence, the goal is to place `x` into its correct sorted position, which is index `x-1`.

1.  **Find the element:** First, we locate the current index of the element `x`.
2.  **Flip to front:** We perform a pancake flip to bring `x` to the front of the array (index 0). The `k`-value for this flip is `index + 1`. This step is skipped if `x` is already at the front.
3.  **Flip to correct position:** With `x` now at the front, we perform a second flip to move it to its final destination at index `x-1`. The `k`-value for this flip is `x`.

After these two flips, the element `x` is in its correct place, and we can effectively ignore it for the rest of the process, reducing the problem size by one. We repeat this for `x-1`, `x-2`, and so on, down to 2. The element 1 will automatically be in place when all other elements are sorted.

This strategy guarantees a solution in at most `2 * (n-1)` flips, which is well within the `10 * n` limit specified by the problem.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> result = new ArrayList<>();
        int n = arr.length;
        for (int valueToSort = n; valueToSort > 0; valueToSort--) {
            // Find the 0-based index of the value we want to place
            int index = findIndex(arr, valueToSort);

            // If the value is already in its correct final position, skip
            if (index == valueToSort - 1) {
                continue;
            }

            // 1. Flip to bring the value to the front (if it's not already there)
            if (index != 0) {
                result.add(index + 1);
                flip(arr, index + 1);
            }

            // 2. Flip to move the value from the front to its correct sorted position
            result.add(valueToSort);
            flip(arr, valueToSort);
        }
        return result;
    }

    private int findIndex(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1; // Should not be reached given problem constraints
    }

    private void flip(int[] arr, int k) {
        int i = 0;
        int j = k - 1;
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
}
```
### Algorithm
- Initialize an empty list `result` to store the k-values.
- Iterate with a variable `valueToSort` from `n` down to `1`, where `n` is the array length.
- In each iteration, find the 0-based index `idx` of `valueToSort` in the array.
- If `idx` is already at the target position (`valueToSort - 1`), do nothing and continue to the next iteration.
- If `valueToSort` is not at the front of the unsorted portion (`idx > 0`), perform a flip with `k = idx + 1` to bring it to the front. Add `idx + 1` to `result`.
- Perform a second flip with `k = valueToSort` to move the element from the front to its correct final position. Add `valueToSort` to `result`.
- After the loop finishes, return the `result` list.

# Solutions
### Java

```java
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 ; } } }
```

### CPP

```cpp
class Solution { public: vector < int > pancakeSort ( vector < int >& arr ) { int n = arr . size (); vector < int > ans ; for ( int i = n - 1 ; i > 0 ; -- i ) { int j = i ; for (; j > 0 && arr [ j ] != i + 1 ; -- j ) ; if ( j == i ) continue ; if ( j > 0 ) { ans . push_back ( j + 1 ); reverse ( arr . begin (), arr . begin () + j + 1 ); } ans . push_back ( i + 1 ); reverse ( arr . begin (), arr . begin () + i + 1 ); } return ans ; } };
```

### Python

```python
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
```