969. Pancake Sorting

// Time: O(n2), Space: O(n)
class Solution {

    // https://leetcode.com/problems/pancake-sorting/discuss/214213/JavaC%2B%2BPython-Straight-Forward
    public List<Integer> pancakeSort(int[] A) {
        List<Integer> result = new ArrayList<>();
        if (A == null || A.length <= 1) {
            return result;
        }

        for (int x=A.length; x>=1; x--) {
            int i=0;
            while (A[i] != x) {
                i++;
            }
            if (i+1 == x) {
                continue;
            }
            reverse(A, i+1);
            reverse(A, x);
            result.add(i+1);
            result.add(x);
        }

        return result;
    }

    public void reverse(int[] A, int k) {
        int i = 0;
        int j = k-1;
        while (i < j) {
            int tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
            i++;
            j--;
        }
    }

    // See solution for mor details
    public List<Integer> pancakeSortMethod2(int[] A) {
        List<Integer> result = new ArrayList<>();
        if (A == null || A.length <= 1) {
            return result;
        }

        int n = A.length;
        Integer[] B = new Integer[n];
        for (int i=0; i<n; i++) {
            B[i] = i+1;
        }
        Arrays.sort(B, (a, b) -> (A[b-1] - A[a-1]));

        for (int b : B) {
            for (int ps : result) {
                if (b <= ps) {
                    b = 1 + (ps-b);
                }
            }

            if (b < n) {
                result.add(b);
                result.add(n);
            }

            n--;
        }

        return result;
    }
}