Pancake Sorting - Practice Coding Problems

Pancake Sorting - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: arr = [3,2,1,4]

› Output: [4,2,4,3]

💡 Note: Flip k=4: [3,2,1,4] → [4,1,2,3]. Flip k=2: [4,1,2,3] → [1,4,2,3]. Flip k=4: [1,4,2,3] → [3,2,4,1]. Flip k=3: [3,2,4,1] → [4,2,3,1]. Continue until sorted.

Example 2 — Already Sorted

$ Input: arr = [1,2,3,4]

› Output: []

💡 Note: Array is already sorted, no flips needed

Example 3 — Reverse Order

$ Input: arr = [4,3,2,1]

› Output: [4,3,2]

💡 Note: Flip k=4: [4,3,2,1] → [1,2,3,4]. But greedy approach: flip k=4 to move 4 to position 0, then flip k=4 to put it at end, then work on [3,2,1]

Constraints

1 ≤ arr.length ≤ 10
1 ≤ arr[i] ≤ arr.length
All integers in arr are unique

Visualization

Tap to expand

Understanding the Visualization

Input Array

Unsorted array [3,2,1,4] with pancake flip operations available

Flip Operations

Can flip prefix of any length k, reversing elements arr[0...k-1]

Sorted Output

Return sequence of k-values that sorts the array

Key Takeaway

🎯 Key Insight: Use a greedy strategy to systematically move the largest unsorted element to its correct position with at most 2 flips per element

Asked in

G Google 25 a Amazon 18 f Facebook 15 M Microsoft 12

The key insight is to systematically place the largest unsorted element in its correct position using at most 2 flips. Best approach is the greedy algorithm which finds the maximum element and moves it to the front (if needed), then flips it to its correct position. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Move Largest Element First	O(n²)	O(1)	Systematically move the largest unsorted element to its correct position
Brute Force - Try All Flip Sequences	O(n! × n²)	O(n)	Generate all possible flip sequences until finding one that sorts the array

Greedy - Move Largest Element First — Algorithm Steps

Start from the last position
Find the largest unsorted element
If not at front, flip it to the front
Flip it to its correct position
Repeat for remaining positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Maximum

Find largest element in unsorted portion

Move to Front

Flip to bring maximum element to front

Move to Position

Flip to move maximum to its correct position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isSorted(int* a, int n) {
    for (int i = 0; i < n - 1; i++) {
        if (a[i] > a[i+1]) return false;
    }
    return true;
}

void flip(int* arr, int k) {
    for (int i = 0; i < k / 2; i++) {
        int temp = arr[i];
        arr[i] = arr[k-1-i];
        arr[k-1-i] = temp;
    }
}

int* solution(int* arr, int n, int* returnSize) {
    if (isSorted(arr, n)) {
        *returnSize = 0;
        return malloc(sizeof(int));
    }
    
    int* result = malloc(2 * n * sizeof(int));
    int resultIdx = 0;
    
    for (int i = n - 1; i > 0; i--) {
        // Find index of maximum element in arr[0:i+1]
        int maxIdx = 0;
        for (int j = 1; j <= i; j++) {
            if (arr[j] > arr[maxIdx]) {
                maxIdx = j;
            }
        }
        
        // If max element is already at position i, continue
        if (maxIdx == i) {
            continue;
        }
        
        // If max element is not at the front, flip it to front
        if (maxIdx != 0) {
            flip(arr, maxIdx + 1);
            result[resultIdx++] = maxIdx + 1;
        }
        
        // Flip to move the max element to position i
        flip(arr, i + 1);
        result[resultIdx++] = i + 1;
    }
    
    *returnSize = resultIdx;
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[100];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        arr[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(arr, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each position n, we search through remaining elements O(n), giving O(n²) total

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra space for variables and result array

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Move Largest Element First — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler