The basic idea is to push the largest element to the end of the array every time. Note that the constraints state that A[i] is a permutation of [1, 2, …, A.length] so we can easily find the largest number at every step. Start from the largest number and find its index in the array, say i. Now, reverse that A[1…i]. This brings the largest number to the start of the array. Now, just reverse the whole array so that the largest number goes to the end of the array. Notice that this takes up only 2 reverses so total number of reverses will be 2*A.length. Further, at each step, we push the largest number to the end of the array and then decrease the size of the array to be considered by 1. Let’s take an example to understand better:
Input: A = [3,2,4,1]
Step 1a: Reverse A[1...largest_num_index] so A = [4,2,3,1]
Step 1b: Reverse A[1...A.length] so A = [1,3,2,4]
Now, the largest number is already in place. In the next step, we will only consider the array A[1...A.length-1]. Largest number in this array becomes 3.
Step 2a: Reverse A[1...largest_num_index] so A = [3,1,2,4]
Step 2b: Reverse A[1...A.length-1] so A = [2,1,3,4]
Step 3a: Reverse A[1...largest_num_index] so A = [2,1,3,4]
Step 3a: Reverse A[1...A.length-2] so A = [1,2,3,4]
The array is sorted now.
class Solution {
public:
vector<int> pancakeSort(vector<int>& A) {
vector<int> res;
for (int i=A.size(); i>1; i--) {
// find index of i
int j;
for (j=0; A[j]!=i; j++);
reverse(A.begin(), A.begin()+j+1);
res.push_back(j+1);
reverse(A.begin(), A.begin()+i);
res.push_back(i);
}
return res;
}
};
Time complexity: O(n*n)