Show problems as
Classic problem #969MediumArrayTwo PointersGreedySorting

Pancake Sorting

Real-world version: Spatula Flips to Sort the Stack
Tracked in this browser only
Read Pancake Sorting on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A cook has a stack of pancakes described by arr, where arr[0] is the pancake on top and arr[len(arr) - 1] the one on the bottom. The pancakes carry the sizes 1 through len(arr), each exactly once.

A flip of depth d slides a spatula under the d-th pancake from the top and turns that whole top portion over, reversing the order of its first d pancakes.

The cook sorts the stack so sizes increase from top to bottom, using this routine. Take the largest size not yet settled. If it is not already in its final place, flip at its depth to bring it to the top, then flip at the depth of its final place to drop it there. A flip is never performed when it would change nothing. Repeat with the next largest size.

Return the depths of the flips the routine performs, in the order it performs them.

Examples

Example 1

Input
arr = [5, 1, 4, 2, 3]
Output
[5, 3, 4, 2, 3, 2]

The size 5 is already on top, so the routine flips at depth 5 to send it to the bottom, then goes on to settle the size 4, and so on down.

Example 2

Input
arr = [1, 2]
Output
[]

Both pancakes already sit in their final places, so no flip is performed.

Example 3

Input
arr = [2, 1]
Output
[2]

The size 2 is already on top, so no flip is needed to bring it up, and a flip of depth 2 sends it to the bottom.

Constraints

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 100
  • arr holds each of the sizes 1 through arr.length exactly once

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def spatula_flips(arr: list[int]) -> list[int]:
Java
public List<Integer> spatulaFlips(int[] arr)

More on the same topics