Pancake Sorting Problem


Description

LeetCode Problem 969.

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).

For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.

Return an array of the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.

Example 1:

1
2
3
4
5
6
7
8
9
Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

Example 2:

1
2
3
4
Input: arr = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Constraints:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= arr.length
  • All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vector<int> result;
        for (int i = 0; i < A.size(); i++) {
           auto maxPosition = max_element(A.begin(), A.end() - i);
           result.push_back(maxPosition - A.begin() + 1);  
           result.push_back(A.size() - i);
           reverse(A.begin(), maxPosition+1);
           reverse(A.begin(), A.end() - i);
        }
        return result;
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Push Dominoes Problem

LeetCode 838. There are n dominoes in a line, and...