Pancake Sorting

Posted: 16 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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

Your task is to sort the array and return all the series of positions from where you flipped the array.

Note:

1. The array given will have elements between 1 to ‘N’, where N is the size of the array, and all elements of the array will be unique.
2. Any valid answer that sorts the array within 10 * array’s length flips will be judged as correct.
3. If the array is already sorted return an empty list. 

For example:

If ARR = [3,2,1] and we performed a pancake flip choosing K = 3, we reverse the sub-array [3,2,1], so ARR = [1,2,3] .  Hence the array becomes sorted therefore return {3}.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer N, where ‘N’ is the number of elements of the array.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output format :

For each test case, return the sequence of flips made.

The output of each test case will be printed in a separate line.

Note:

You don’t need to print anything. You just need to implement the given function.

Constraints:

1 <= T <= 5
1 <=  N <= 100
1 <= ARR[i] < N

Time Limit: 1 second
Approach 1

The main idea to solve this problem is that if we want to place a number at an index, then we need a maximum of 2 moves that are:- 

 

  1. Bring it to the 0th index by reversing the prefix array till its index, e.g., if you chose some index K, then reverse the array from 0th index till Kth index.
  2. Reverse the prefix array from the 0th index to the index where we want to place it.
  • The main algorithm runs a loop over the values of the list, starting from the largest one.
    • At each round, we identify the value to sort (named as ‘NUM_TO_FIND’), which is the number we would put in place at this round.
    • We then locate the index of the ‘NUM_TO_FIND.’
    • If the ‘NUM_TO_FIND’ is not at its place already, we can then perform at most two pancake flips as we explained above.
    • At the end of the round, the ‘NUM_TO_FIND’ would be put in place.
  • At each flip, push the index in a resultant array.
  • Return the resultant array after the given array is sorted.
Try Problem