[LeetCode] 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.

Example:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

Input: arr = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Constraints:

• 1 <= arr.length <= 100
• 1 <= arr[i] <= arr.length
• All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

Approach: We can try something like bubble sort approach where we put the maximum element at the end of the array. But how we do it? We are not allowed to swap, Right? We can only apply above Flip operation which basically reverse the sub array  [0...k - 1].

Let's see how we can use Flip. We find the index of maximum number say 'i'. Once we got it, we flip [0...i]. Now our maximum number is at the head. Now simply we can flip the whole array to take maximum number to last index.

Now we keep doing it for rest of the elements in descending order and apply these Flips. Please note that not every time we Flip the whole array as we know the maximum number is already in place so we decrease the last index by 1 every time we place the element to its right position.

That's all!

Implementation in C#:

    public IList<int> PancakeSort(int[] arr)

    {

        if (arr == null || arr.Length <= 1)

        {

            return new List<int>();

        }

        List<int> result = new List<int>();

        for (int i = arr.Length; i >= 1; --i)

        {

            int index = this.FindIndex(arr, i);

            if (index == i - 1)

            {

                continue;

            }

            if (index != 0)

            {

                result.Add(index + 1);

                this.Flip(arr, index);

            }

            result.Add(i);

            this.Flip(arr, i - 1);

        }

        return result;

    }

    private void Flip(int[] arr, int index)

    {

        int start = 0, end = index;

        while (start < end)

        {

            int temp = arr[start];

            arr[start] = arr[end];

            arr[end] = temp;

            ++start;

            --end;

        }

    }

    private int FindIndex(int[] arr, int element)

    {

        for (int i = 0; i < arr.Length; ++i)

        {

            if (arr[i] ==  element)

            {

                return i;

            }

        }

        return -1;

    }

Complexity: O(n^2)