Pancake sorting

Array Two Pointers Greedy Sorting

71.7% acceptance

Feb 25, 2026

1596

1559

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn pancake_sort(arr: Vec<i32>) -> Vec<i32> {
    let mut arr = arr;
    let n = arr.len();
    let mut res = Vec::new();
    for size in (1..=n).rev() {
      // Find position of max element in arr[0..size]
      let max_pos = arr[..size].iter().enumerate().max_by_key(|&(_, &v)| v).map(|(i, _)| i).unwrap();
      if max_pos == size - 1 { continue; }
      if max_pos != 0 {
        // Flip to bring max to front
        arr[..=max_pos].reverse();
        res.push(max_pos as i32 + 1);
      }
      // Flip to bring max to its correct position
      arr[..size].reverse();
      res.push(size as i32);
    }
    res
  }
}