Approach 1: Sort Largest to Smallest
We can place the largest element (in location
i, 1-indexed) 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 pancake-flip by
A.length or more.
We can repeat this process until the array is sorted. Each move will use 2 flips per element.
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
i <= f, then the element has moved from location
f+1 - i.
After, we flip by
N-- to put this element in the correct position.
Time Complexity: , where is the length of
Space Complexity: .