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

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.

Examples

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,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]

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

Thinking Process

  1. Greedy Strategy: Place largest elements first, working from right to left
    • First flip: Bring target element to front (if not already there)
    • Second flip: Move target element to its correct position
  • Greedy works when local optimal choices lead to global optimum.
  • Often sort first to make the greedy choice obvious.
  • Prove or sanity-check: would swapping two choices ever help?
Greedy choice pick locally best after sorting

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Sort + greedy (this problem) O(n log n) O(1) Interval scheduling, assignment
Local greedy choice O(n) O(1) Jump game, gas station
Greedy + heap O(n log n) O(n) Merge streams, room allocation
Exchange argument O(n) O(1) Prove greedy choice is safe

Solution

Time Complexity: O(n²) - For each of n elements, we may need to search and flip
Space Complexity: O(1) excluding output array

The key insight is to use a greedy strategy: place the largest unsorted element in its correct position, then work on the next largest, and so on.

Solution: Greedy with Helper Functions

class Solution {
    public void flip(int[] subarr, int k) {
        int i = 0;
        while(i < k / 2) {
            int tmp = subarr[i];
            subarr[i] = subarr[k - i - 1];
            subarr[k - i - 1] = tmp;
            i++;
        }
    }
        public int find(int[] arr, int target) {
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] == target) return i;
        }
        return -1;
    }
    int[]pancakeSort(int[] arr) {
        List<Integer> rtn = new ArrayList<>();

        for(int valueToSort = arr.length; valueToSort > 0; valueToSort--) {
            int idx = find(arr, valueToSort);

            if(idx == valueToSort - 1) continue;

            if(idx !) {
                rtn.add(idx + 1);
                flip(arr, idx + 1);
            }

            rtn.add(valueToSort);
            flip(arr, valueToSort);
        }

        return rtn;
    }
}

Solution Explanation

Approach: Sort + greedy (this problem)

Key idea: 1. Greedy Strategy: Place largest elements first, working from right to left

How the code works:

  1. Greedy Strategy: Place largest elements first, working from right to left
    • First flip: Bring target element to front (if not already there)
    • Second flip: Move target element to its correct position
    • Greedy works when local optimal choices lead to global optimum.
    • Often sort first to make the greedy choice obvious.
    • Prove or sanity-check: would swapping two choices ever help?

Walkthrough — input arr = [3,2,4,1], expected output [4,2,4,3]:

We perform 4 pancake flips, with k values [4,2,4,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]

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | Greedy with Linear Search | O(n²) | O(1) | Simple, clear | O(n) find per element | | Java Collections max_element | O(n²) | O(1) | Cleaner code | Iterator complexity | | Position Map | O(n²) | O(n) | O(1) find | More complex |

Algorithm Breakdown

class Solution {
    public int[] pancakeSort(int[] arr) {
        List<Integer> result = new ArrayList<>();

        for(int size = arr.length; size > 1; size--) {
            // Find index of maximum in unsorted portion
        int maxIdx = max_element(arr.iterator(), arr.iterator() + size) - arr.iterator();

            if(maxIdx == size - 1) continue;  // Already in place

            // Bring max to front
            if(maxIdx > 0) {
                result.add(maxIdx + 1);
                reverse(arr.iterator(), arr.iterator() + maxIdx + 1);
            }

            // Move max to correct position
            result.add(size);
            reverse(arr.iterator(), arr.iterator() + size);
        }

        return result;
    }
}

Helper Functions

Flip Function:

class Solution {
    public int[] pancakeSort(int[] arr) {
        List<Integer> result = new ArrayList<>();
        int n = arr.length;

        // Create position map: value . index
        int[]pos(n + 1);
        for(int i = 0; i < n; i++) {
            pos[arr[i]] = i;
        }

        for(int val = n; val >= 1; val--) {
            int idx = pos[val];

            if(idx == val - 1) continue;

            if(idx !) {
                result.add(idx + 1);
                flip(arr, idx + 1, pos);
            }

            result.add(val);
            flip(arr, val, pos);
        }

        return result;
    }
    public void flip(int[] arr, int k, int[] pos) {
        for(int i = 0; i < k / 2; i++) {
            swap(arr, i, k - 1 - i);
            pos[arr[i]] = i;
            pos[arr[k - 1 - i]] = k - 1 - i;
        }
    }
}

Reverses the first k elements by swapping elements from both ends.

Find Function:

int find(vector<int>& arr, int target) {
    for(int i = 0; i < arr.size(); i++) {
        if(arr[i] == target) return i;
    }
    return -1;  // Should never happen given constraints
}

Linear search to find the index of target value.

Complexity

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | Greedy with Linear Search | O(n²) | O(1) | Simple, clear | O(n) find per element | | Java Collections max_element | O(n²) | O(1) | Cleaner code | Iterator complexity | | Position Map | O(n²) | O(n) | O(1) find | More complex |

Implementation Details

Flip Operation

void flip(vector<int>& subarr, int k) {
    int i = 0;
    while(i < k / 2) {
        swap(subarr[i], subarr[k - i - 1]);
        i++;
    }
}

Why k / 2?

  • We only need to swap up to the middle
  • Swapping i with k-i-1 handles both ends
  • When i >= k/2, all pairs are swapped

Index Conversion

rtn.push_back(idx + 1);  // Convert 0-indexed to 1-indexed

The problem uses 1-indexed k (flip first k elements), but arrays are 0-indexed.

Early Termination

if(idx == valueToSort - 1) continue;

If element is already in correct position, skip both flips to optimize.

Common Mistakes

  1. Already sorted: [1,2,3] → return []
  2. Reverse sorted: [3,2,1] → requires flips
  3. Single element: [1] → return []
  4. Element at front: [4,1,2,3] → skip first flip

  5. Element in place: Skip both flips

  6. Off-by-one errors: Using idx instead of idx + 1 for k
  7. Wrong flip condition: Not checking if idx != 0 before first flip
  8. Incorrect position check: Using idx == valueToSort instead of idx == valueToSort - 1
  9. Missing continue: Not skipping when element is already in place
  10. Wrong loop direction: Processing smallest to largest instead of largest to smallest

Optimization Tips

  1. Skip Already Sorted: Check if element is in place before flipping
  2. Position Map: Use hash map for O(1) find instead of O(n) linear search
  3. Early Exit: If array becomes sorted, stop early
  4. Java Collections Functions: Use reverse() and max_element() for cleaner code

Real-World Applications

  1. Network Routing: Reordering packets with limited operations
  2. Database Operations: Optimizing query execution order
  3. Game Theory: Puzzles and optimization problems
  4. Algorithm Design: Understanding constraint-based sorting

Pattern Recognition

This problem demonstrates the “Greedy Sorting with Constraints” pattern:

1. Identify target element (largest unsorted)
2. Bring to front (if needed)
3. Move to correct position
4. Repeat for next target

Similar problems:

  • Sorting with limited operations
  • Constraint-based optimization
  • Greedy algorithms

Why Greedy Works

  1. Optimal Substructure: Placing largest element correctly doesn’t affect smaller elements
  2. Greedy Choice: Always placing largest unsorted element is optimal
  3. No Future Dependencies: Decisions don’t depend on future placements
  4. Constraint Satisfaction: Each flip brings us closer to sorted state

Pancake Sorting Theory

  • Minimum Flips: Finding minimum flips is NP-hard
  • Upper Bound: At most 2n - 3 flips needed (proven)
  • Greedy Bound: This algorithm uses at most 2n flips
  • Optimal: For small arrays, can find optimal solution

This problem is a fun introduction to constraint-based sorting, demonstrating how greedy algorithms can solve seemingly complex problems with simple strategies.

Key Takeaways

  1. Greedy Strategy: Place largest elements first, working from right to left
  2. Two-Step Process:
    • First flip: Bring target element to front (if not already there)
    • Second flip: Move target element to its correct position
  3. Skip Optimization: If element is already in correct position, skip it
  4. Index Conversion: k is 1-indexed (flip first k elements), but arrays are 0-indexed
  5. Unique Values: Since all values are unique, find always returns a valid index

References

Template Reference