LeetCode Medium: Pancake Sorting

Problem of the day: Pancake Sorting

Problem description: https://leetcode.com/problems/pancake-sorting/

Solution Approach:

At every iteration for n-1 iterations move the max element in unsorted prefix array to the end of it by following the following steps:

1. Find max element index in unsorted prefix part.
2. flip array at that index.
3. flip array at index marking the end of unsorted array.
4. reduce the pointer marking end of unsorted array by 1 thereby decreasing the unsorted part of the array.

Solution:

  
  class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        if (arr.length<=1) {
            return new ArrayList<>();
        }
        
        List<Integer> maxIndicesSelectedForFlip;
        
        int endOfUnsortedArray = arr.length-1;
        for (int idx=1; idx <= endOfUnsortedArray; idx++) {
            //find maxElement, maxElementIndex
            int maxElement = Integer.MIN_VALUE, maxElementIndex = -1;
            for (int i=0; i < endOfUnsortedArray; i++) {
                if (arr[i]>maxElement) {
                    maxElement = arr[i];
                    maxElementIndex = i;
                }
            }

            //Flip 0->maxElementIndex
            flip(arr, maxElementIndex);
            maxIndicesSelectedForFlip.add(maxElementIndex+1);

            //Flip 0->endOfUnsortedArray
            flip(arr, endOfUnsortedArray);
            maxIndicesSelectedForFlip.add(endOfUnsortedArray+1);
        }
        
        return maxIndicesSelectedForFlip;
        
    }
    
    private void flip(int[] arr, int maxIndex) {
        for (int i=0; i<=maxIndex/2; i++) {
            int tmp = arr[i];
            arr[i] = arr[maxIndex-i];
            arr[maxIndex-i] = tmp;
        }
    }
    
}
  
  

Time Complexity: O(n^2)

Space Complexity: In-place sorting: O(1) 

Happy Coding! ;)