Pancake Sorting: Flip Your Way to Order

Approach

Since we can only flip the first N elements, we work backwards. We put the largest element in place first, then the second largest, and so on.

Optimal Solution

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vector<int> res;
        for(int i=0;i<A.size()-1;i++) {
            auto maxPos = max_element(A.begin(), A.end()-i);
            res.push_back(maxPos-A.begin()+1);
            res.push_back(A.size()-i);
            reverse(A.begin(), maxPos+1);
            reverse(A.begin(), A.end()-i);
        }
        
        return res;
    }
};

Key Takeaways

STL’s max_element returns the address where the maximum value lives. The iterators begin() and end() give you the address of the first element and one past the last element respectively.

To flip an array: reverse(start_address, end_address + 1).

#sort #array #stl #iterator