1import java.util.*;
2
3public class PancakeSort {
4    public static List<Integer> pancakeSort(int[] arr) {
5        List<Integer> result = new ArrayList<>();
6        for (int i = arr.length - 1; i > 0; i--) {
7            int maxIndex = findMaxIndex(arr, i);
8            if (maxIndex != i) {
9                if (maxIndex != 0) {
10                    reverse(arr, maxIndex);
11                    result.add(maxIndex + 1);
12                }
13                reverse(arr, i);
14                result.add(i + 1);
15            }
16        }
17        return result;
18    }
19
20    private static void reverse(int[] arr, int k) {
21        int i = 0;
22        while (i < k) {
23            int temp = arr[i];
24            arr[i] = arr[k];
25            arr[k] = temp;
26            i++;
27            k--;
28        }
29    }
30
31    private static int findMaxIndex(int[] arr, int n) {
32        int maxIndex = 0;
33        for (int i = 0; i <= n; i++) {
34            if (arr[i] > arr[maxIndex]) {
35                maxIndex = i;
36            }
37        }
38        return maxIndex;
39    }
40
41    public static void main(String[] args) {
42        int[] arr = {3, 2, 4, 1};
43        List<Integer> flips = pancakeSort(arr);
44        flips.forEach(f -> System.out.print(f + " "));
45    }
46}