You are given an array arr consisting of a permutation of numbers from 1 to n. Your task:

Return a sequence of pancake flips that will sort the array in ascending order.

Definition:

A pancake flip of k means reversing the subarray arr[0..k-1].

Example:

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

Explanation:
Applying flips in output order will transform the array into [1,2,3,4].

Another example:

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

Already sorted → no flips needed.

---

Problem Understanding

Important details:

• Only one operation is allowed: reverse from index 0 to k-1
• You must produce any valid sequence — not necessarily minimal
• arr contains all numbers from 1 to n exactly once
• The goal is to sort in increasing order

Key idea:

Pancake sorting mimics selection sort

Instead of swapping directly, we use flips to move the next largest value into correct position.

---

Logic Explained in Simple English

Think of the process like placing pancakes on a plate:

1. Find the largest unsorted number.
2. Bring it to the top using a flip.
3. Flip again to move it to its correct position at the bottom of the unsorted region.
4. Reduce the region and repeat.

Example:

To place value n at index n-1:

• Flip at its current index to bring it to front
• Flip at size n to move it to end

Why this works:

• Each number is positioned correctly in two flips
• Sorted portion grows from the end backward
• Process continues until array sorted

Total flips worst-case:

2 * n

Which is acceptable.

---

Step-by-Step Approach

1. Initialize an empty result list
2. For target n decreasing from arr.length down to 1:
   • Find index of value target
   • If index == target-1 → already in correct position, continue
   • If index != 0:
     • flip(index+1) to bring target to front
   • flip(target) to move it into correct position
   • append flip values to result
3. Return result

---

Java Implementation

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> result = new ArrayList<>();
        int n = arr.length;
        
        for (int target = n; target > 0; target--) {
            int index = findIndex(arr, target);
            
            if (index == target - 1) {
                continue;
            }
            
            if (index != 0) {
                flip(arr, index + 1);
                result.add(index + 1);
            }
            
            flip(arr, target);
            result.add(target);
        }
        
        return result;
    }
    
    private int findIndex(int[] arr, int value) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value) return i;
        }
        return -1;
    }
    
    private void flip(int[] arr, int k) {
        int left = 0;
        int right = k - 1;
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

---

Dry Run Example

Input:

[3,2,4,1]

Pass 1 — target = 4

Find index of 4 → index = 2
Flip(3):

[4,2,3,1]

Flip(4):

[1,3,2,4]  (now 4 in correct place)

Pass 2 — target = 3

Find index of 3 → index = 1
Flip(2):

[3,1,2,4]

Flip(3):

[2,1,3,4]

Pass 3 — target = 2

Find index of 2 → index = 0
Flip(2):

[1,2,3,4]

Now sorted.

Output flips:

[3,4,2,3,2]

Any valid sequence like this is acceptable.

---

Time and Space Complexity

Time Complexity

O(n²)

Because findIndex scans array for each target.

Space Complexity

O(1)

Only in-place modifications, aside from output list.

---

Common Mistakes and How to Avoid Them

Mistake 1: Trying to minimize flips

Not required — any valid solution accepted.

Mistake 2: Flipping even when value already in place

Check:

if index == target - 1 → skip

Mistake 3: Forgetting second flip

Two flips needed unless already at front.

Mistake 4: Off-by-one errors in flip size

flip takes k, affecting indices [0..k-1]

Mistake 5: Sorting values instead of permutation logic

Array contains exact values 1..n, simplifying target detection.