Problem Explanation

Given an unsorted array, you are allowed to reverse the order of the first k elements (k <= number of elements in the array) of the array, and this operation is known as a pancake flip. You have to sort this array using the above operation and return the k values.

Let's take an example: If the array is [3, 2, 4, 1]. The sequence of pancake flips is [4, 2, 4, 3]. The array can be sorted from highest to lowest using these steps:

Original array: [3, 2, 4, 1]

After 1st flip (k=4): [1, 4, 2, 3]

After 2nd flip (k=2): [4, 1, 2, 3]

After 3rd flip (k=4): [3, 2, 1, 4]

After 4th flip (k=3): [1, 2, 3, 4] -> This is sorted array.

For each unplaced element from the largest target to the smallest 1, there are two steps to put target at its final position:

1. Locate the position i of target and do a pancake flip at i + 1 to move target to the beginning.
2. Then do a pancake flip at target to move target to its final position.

Solution in Python

1
2python
3class Solution:
4    def pancakeSort(self, arr):
5        ans = []
6
7        for target in range(len(arr), 0, -1):
8            i = arr.index(target)
9            arr[:i+1] = reversed(arr[:i+1])
10            arr[:target] = reversed(arr[:target])
11            ans += [i+1, target]
12
13        return ans

Solution in Java

1
2java
3class Solution {
4    public List<Integer> pancakeSort(int[] arr) {
5        List<Integer> ans = new ArrayList();
6
7        for (int target = arr.length; target > 0; target--) {
8            int i;
9            for (i = 0; arr[i] != target; i++);
10            reverse(arr, i + 1);
11            reverse(arr, target);
12            ans.add(i + 1);
13            ans.add(target);
14        }
15
16        return ans;
17    }
18
19    public void reverse(int[] arr, int k) {
20        for (int i = 0, j = k - 1; i < j; i++, j--) {
21            int tmp = arr[i];
22            arr[i] = arr[j];
23            arr[j] = tmp;
24        }
25    }
26}

Solution in Javascript

1
2javascript
3var pancakeSort = function(arr) {
4    const res = [];
5
6    for(let target = arr.length; target > 0; target--) {
7        let i;
8        for(i = 0; arr[i] !== target; i++);
9        reverse(arr, 0, i);
10        reverse(arr, 0, target - 1);
11        res.push(i + 1);
12        res.push(target);
13    }
14
15    return res;
16};
17
18function reverse(arr, i, j) {
19    while(i < j) {
20        const temp = arr[i];
21        arr[i] = arr[j];
22        arr[j] = temp;
23        i++;
24        j--;
25    }
26};

Solution in C++

1
2c++
3class Solution {
4public:
5    vector<int> pancakeSort(vector<int>& arr) {
6        vector<int> ans;
7        
8        for (int target = arr.size(); target > 0; --target) {
9            auto it = find(arr.begin(), arr.end(), target);
10            reverse(arr.begin(), it + 1);
11            ans.push_back(distance(arr.begin(), it + 1));
12            reverse(arr.begin(), arr.begin() + target);
13            ans.push_back(target);
14        }
15        
16        return ans;
17    }
18};

Solution in C#

1
2c#
3public class Solution {
4    public IList<int> PancakeSort(int[] arr) {
5        var ans = new List<int>();
6
7        for (int target = arr.Length; target > 0; target--) {
8            int i = Array.IndexOf(arr, target);
9            reverse(arr, i + 1);
10            reverse(arr, target);
11            ans.Add(i + 1);
12            ans.Add(target);
13        }
14        
15        return ans;
16    }
17    
18    private void reverse(int[] arr, int k) {
19        for (int i = 0, j = k - 1; i < j; i++, j--) {
20            var tmp = arr[i];
21            arr[i] = arr[j];
22            arr[j] = tmp;
23        }
24    }
25}

A helpful point to remember is that the algorithm doesn't work by placing the smallest elements first but by placing the largest elements at their correct places as early as possible. In practice, this saves a lot of unnecessary operations because once a big number is in its place, it doesn't move anymore.# Solution in Ruby

Here's another solution implemented in Ruby for the same problem. The Array#index method in Ruby returns the index of the first element that matches the one provided.

1
2ruby
3def pancake_sort(arr)
4  ans = []
5  
6  for target in (arr.length).downto(1)
7    i = arr.index(target)
8    arr[0..i] = arr[0..i].reverse
9    arr[0...target] = arr[0...target].reverse
10    ans += [i+1, target]
11  end
12
13  ans
14end

This Ruby method works by first finding the target value in the array, then reversing the first i+1 elements to bring the target to the start of the array. It then reverses the first i elements to bring the target to its final position. This process is repeated until all the elements of the array are sorted in ascending order.

The solutions presented above should have given you a good understanding of how to solve this problem in multiple languages. Remember that you can play around with the code to get a better understanding of how it works. The most important part is to have the logic of the problem clear in your mind. Once you have that, implementing the solution becomes a lot simpler.

Remember, practice is the key to mastering any programming language. So try to work on as many coding problems as you can in the language you are comfortable with and then slowly try implementing the same solutions in other languages to increase your skill-set. Happy coding!