Given an array of integers arr:

Write a function flip(arr, k) that reverses the order of the first k elements in the array arr.

Write a function pancakeSort(arr) that sorts and returns the input array.

You are allowed to use only the function flip you wrote in the first step in order to make changes in the array.

Example:

input: arr = [1, 5, 4, 3, 2]

output: [1, 2, 3, 4, 5] # to clarify, this is pancakeSort's output

My approach:

import java.io.*;
import java.util.*;

class Solution 

 static int pancakeSort(int arr) 
 // your code goes here
 int max = -1000,maxpos = 0 ;
 //3 1 2 4 6 5 --> 6 4 2 1 3 5
 for(int i = 0; i < arr.length; i++ )
 
 max = -1000;
 for( int c = i; c < arr.length; c++ )
 
 if( max <= arr[c] )
 
 max = arr[c];
 maxpos = c;
 
 
 arr = flip(arr,i,maxpos+1);
 
 arr = flip(arr,0,arr.length);
 return arr; 
 

 // 3 1 2 4 6 -> 6 4 2 1 3 5
 // k = 5 ->
 static int flip(int arr,int start , int k)
 
 int temp;

 for(int i = start, j = k - 1; i < j; i++, j-- )
 
 temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 
 return arr;
 

 // 
 //1 5 4 3 -> 3 4 5 1
//54321

 1 5 4 3 2 --> flip(arr, maxpos) -> 5 1 4 3 2 --> flip(arr,arr.length ) -> 2 3 4 1 5

 public static void main(String args) 

 

I have the following questions about my code:

1. Can I further improve my space and time complexity?




2. Is there any other alternative, smarter way to attempt this question?




3. Any grave coding convention that I have violated in my code?

Reference

Flip

• Use better variable names. i and j are harder to read than something like front and back.




• It's preferable to define the temp value inside the loop and save a line of code.




• The method should be private.




• Depending on what the interviewer wants, it's much nicer to make a new array than to destructively modify the existing one. I'll assume you asked and they specified to modify the existing array. That being the case, you don't need to return the modified array.

Pancake Sort

• You're not doing a pancake sort. It's nonsensical for you to describe a problem and then ask us to review code that breaks your own stated invariants to solve the problem.




• -1000 is arbitrary. Use Integer.MIN_VALUE and your code will work for all negative numbers.




• Don't use abbreviations or shorten variable names. The extra letters don't cost anything. max and maxPos are not sufficiently descriptive. Don't use c as an array index. Either use j or a descriptive name.




• In the comments, you observe that pancake sort is inefficient. Yes, it is. The point was to pick a sort that most people haven't thought about so everybody starts on an even playing field for the interview question. The inefficiency is tied to the algorithmic limitation of only having flip() available. There are no significant performance gains to be had unless you break that limitation, at which point you're no longer doing a pancake sort.

Using an actual pancake sort and my other suggestions, your code might look something like:

class Solution 

 // return an int for convenient testing
 private static int pancakeSort(final int array) 
 boolean sorted = false;
 while (!sorted) 
 sorted = true;
 for (int i = 0; i < (array.length - 1); i++) 
 if (array[i] > array[i + 1]) 
 flip(array, i + 1);
 flip(array, i + 2);
 flip(array, i + 1);
 sorted = false;
 break;
 
 
 
 return array;
 

 private static void flip(final int array, final int elementsToFlip) 
 for (int front = 0, back = elementsToFlip - 1; front < back; front++, back--) 
 final int temp = array[front];
 array[front] = array[back];
 array[back] = temp;
 
 

 public static void main(final String args) 
 System.out.println(Arrays.toString(pancakeSort(new int 1 )));
 System.out.println(Arrays.toString(pancakeSort(new int 1, 2 )));
 System.out.println(Arrays.toString(pancakeSort(new int 2, 1 )));
 System.out.println(Arrays.toString(pancakeSort(new int 1, 2, 3 )));
 System.out.println(Arrays.toString(pancakeSort(new int 2, 1, 3 )));
 System.out.println(Arrays.toString(pancakeSort(new int 3, 1, 2 )));
 System.out.println(Arrays.toString(pancakeSort(new int 3, 2, 1 )));
 System.out.println(Arrays.toString(pancakeSort(new int 3, 2, 1, 8, 4, 6, 5, 10, 7, 9 )));
 

Eric has given some good points, though I would implement it differently, something like:

public static void pancakeSort(final int array) 
 for (int remainingToSort = array.length; remainingToSort >= 2; remainingToSort--) 
 int maxValue = array[0];
 int maxIndex = 0;
 for (int i = 1; i < remainingToSort; i++) 
 if (array[i] > maxValue) 
 maxValue = array[i];
 maxIndex = i;
 
 
 if (maxIndex != remainingToSort - 1) 
 // flip max to the top of the stack
 flip(array, maxIndex + 1);
 // flip max to the bottom of the remaining stack to sort
 flip(array, remainingToSort);
 
 

The reason for this is that now we only flip while it is necessary, because if the bottom of the remaining stack already contains the largest pancake, we do not need to flip. Meanwhile, we are also keeping the implementation clear: you first look for the largest pancake in the remaining to sort stack, move it to the top, and then to the bottom of the remaining stack. Using clear variable names makes it so other people can understand your implementation more easily (and even for yourself, if you would come back later).