Pancake Sorting

Easy
0/40
Average time to solve is 15m
10 upvotes
Asked in companies
UberWalmartalibaba

Problem statement

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}.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
3
3 2 1 
4
4 1 2 3

Sample Output 1 :

3
4 3

Explanation of the Sample Input 1:

For the first test case:
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.

For the second test case:
We first chose index 4, which made the array after reversing [3, 2, 1, 4]. Then we chose index 3 and reversed it hence giving the array [1, 2, 3, 4], which is sorted.

Sample Input 2 :

2
4
3 4 1 2 
5
5 3 4 1 2

Sample Output 2 :

2 4 2 
5 3 4 3
Hint

Fix one element at a time.

Approaches (1)
Pancake Sorting.

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.
Time Complexity

O(N ^ 2), where ‘N’ is the length of the given array.

 

We find the index of every element and rotate the array two times max. Therefore, net time complexity will be O(N ^ 2).

Space Complexity

O(1).

 

Since we are not using any extra space to keep track of the elements.

Code Solution
(100% EXP penalty)
Pancake Sorting
Full screen
Console