Algorithm
Problem Name: 969. Pancake Sorting
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
kwhere1 <= 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.
Example 2:
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 <= 1001 <= arr[i] <= arr.length- All integers in
arrare unique (i.e.arris a permutation of the integers from1toarr.length).
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List pancakeSort(int[] arr) {
List result = new ArrayList<>();
for (int i = arr.length; i > 0; i--) {
int idx = findIdx(arr, i);
if (idx != i - 1) {
if (idx != 0) {
result.add(idx + 1);
flip(arr, idx + 1);
}
result.add(i);
flip(arr, i);
}
}
return result;
}
private void flip(int[] arr, int k) {
for (int i = 0; i < k / 2; i++) {
int temp = arr[i];
arr[i] = arr[k - i - 1];
arr[k - i - 1] = temp;
}
}
private int findIdx(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const pancakeSort = function (arr) {
const res = []
let n = arr.length
while(n) {
const idx = indexOf(0, n - 1, n)
if(idx === n - 1) {
n--
} else {
flip(0, idx)
flip(0, n - 1)
res.push(idx + 1, n)
n--
}
}
return res
function flip(l, r) {
while(l < r) {
const tmp = arr[l]
arr[l] = arr[r]
arr[r] = tmp
l++
r--
}
}
function indexOf(start, end, target) {
let res = -1
for(let i = start; i < = end; i++) {
if(arr[i]===target> {
res = i
break
}
}
return res
}
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def pancakeSort(self, A):
res = []
for x in range(len(A), 1, -1):
i = A.index(x)
res.extend([i + 1, x])
A = A[:i:-1] + A[:i]
return res
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0969_PancakeSorting
{
public IList < int> PancakeSort(int[] A)
{
var result = new List<int>();
for (int x = A.Length; x > 0; x--)
{
int index = 0;
while (A[index] != x) index++;
if (index + 1 == x) continue;
Flip(A, index + 1);
result.Add(index + 1);
Flip(A, x);
result.Add(x);
}
return result;
}
private void Flip(int[] a, int k)
{
for (int i = 0, j = k - 1; i < j; i++, j--)
{
var temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
Input
Output