Solution to Leetcode problem 969 Pancake Sorting

This is the second problem of Leetcode contest 118. I thought this was actually a very interesting problem because there are probably many different ways of solving it. Thankfully, we are not asked to sort the array in a minimum number of moves.

Problem statement of Leetcode 969

Given an array A, you are given an array transformation called “flip”. You can flip the first k elements ( 1 <= k <= A.length), and it will reverse the order of the first k elements of A.

The elements in the array are 1,2,…,A.length. You should return a series of flips such that A is sorted in the end.

The approach I took in the end is quite simple. What I do to sort the array is

• For the subarray A[0,1,…,k], put the integer k+1 in the k-th position (index k).
• Sort the subarray A[0,1,…,k-1]

Of course, we stop when k=0. To put k+1 in the k-th position, I do the following:

• Find k+1 at index i. This is done in the method indexOf().
• Flip the subarray A[0,i] to put k+1 in the first position (index 0). flip() is implemented to keep track of the state of A while we sort it.
• Flip the subarray A[0,k] to put k+1 is the k-th position (index k)

class Solution {
    public List<Integer> pancakeSort(int[] A)…