Solution
Approach 1: Sort Largest to Smallest
Intuition
We can place the largest element (in location i
, 1indexed) by flipping i
to move the element to the first position, then A.length
to move it to the last position. Afterwards, the largest element is in the correct position, so we no longer need to pancakeflip by A.length
or more.
We can repeat this process until the array is sorted. Each move will use 2 flips per element.
Algorithm
First, sort the locations from largest value of A to smallest value of A.
For each element (from largest to smallest) with location i
, we will first simulate where this element actually is, based on the pancake flips we have done. For a pancake flip f
, if i <= f
, then the element has moved from location i
to f+1  i
.
After, we flip by i
then N
to put this element in the correct position.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .