In this guide, you will get 969. Pancake Sorting LeetCode Solution with the best time and space complexity. The solution to Pancake Sorting problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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:
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.
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).
Complexity Analysis
Time Complexity:
Space Complexity:
969. Pancake Sorting LeetCode Solution in C++
class Solution {
public:
vector<int> pancakeSort(vector<int>& arr) {
vector<int> ans;
for (int target = arr.size(); target >= 1; --target) {
int index = find(arr, target);
reverse(arr.begin(), arr.begin() + index + 1);
reverse(arr.begin(), arr.begin() + target);
ans.push_back(index + 1);
ans.push_back(target);
}
return ans;
}
private:
int find(vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); ++i)
if (arr[i] == target)
return i;
throw;
}
}; /* code provided by PROGIEZ */
969. Pancake Sorting LeetCode Solution in Java
class Solution {
public List<Integer> pancakeSort(int[] arr) {
List<Integer> ans = new ArrayList<>();
for (int target = arr.length; target >= 1; --target) {
int index = find(arr, target);
reverse(arr, 0, index);
reverse(arr, 0, target - 1);
ans.add(index + 1);
ans.add(target);
}
return ans;
}
private int find(int[] arr, int target) {
for (int i = 0; i < arr.length; ++i)
if (arr[i] == target)
return i;
throw new IllegalArgumentException();
}
private void reverse(int[] arr, int l, int r) {
while (l < r)
swap(arr, l++, r--);
}
private void swap(int[] arr, int l, int r) {
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
} // code provided by PROGIEZ
969. Pancake Sorting LeetCode Solution in Python
class Solution:
def pancakeSort(self, arr: list[int]) -> list[int]:
ans = []
for target in range(len(arr), 0, -1):
index = arr.index(target)
arr[:index + 1] = arr[:index + 1][::-1]
arr[:target] = arr[:target][::-1]
ans.append(index + 1)
ans.append(target)
return ans # code by PROGIEZ
