Solving ‘pancakeSort’ in JavaScript

In this article, I’ll be breaking down the pancakeSort problem in a few different ways in JavaScript. Then I’ll walk through my process of solving the problem and discuss its BigO.

Let’s begin!

Question

Given an array of integers arr:

1. Write a function flip(arr, k) that reverses the order of the first k elements in the array arr.
2. 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]

Note: it’s called pancake sort because it resembles sorting pancakes on a plate with a spatula, where you can only use the spatula to flip some of the top pancakes on the plate. To read more about the problem, see the Pancake Sorting Wikipedia page.

Let's analyze the problem.

We need to create and use a flip function that sorts the array given to us — furthermore, this flip function can only flip the first k values within the array passed to it.

Knowing this, how do we utilize this helper function in sorting our array?

Well… if you took a look at the note you might’ve guessed it — we’ll use Pancake Sorting.

The way we’ll implement this is by determining what sections of the array we need to flip in order to place the values according to lowest to highest.

Within a loop:

Step 1: Find the index of the value in the array with the max value

Step 2: Flip the array from index 0 to the index of the max value

Step 3: Flip the array AGAIN from index 0 to the index right before the previous ‘max value’ ** if it's the first iteration the index we flip to would be array.length-1, for the next iteration it would be to array.length-2, and so on.

This sounds weird. Let’s take an actual look at how that would work:

• array to be flipped →[ 1, 5, 4, 3, 2 ] → maxInd = 1 → flip from index 0 to index 1 → array returned after first flip → [ 5, 1, 4, 3, 2 ] → next index to flip to is arr.length-1 → array returned from both flips → [ 2, 3, 4, 1, 5 ]
• array to be flipped → [ 2, 3, 4, 1, 5 ] → maxInd = 2 → flip from index 0 to index 2 → array returned after first flip → [ 4, 3, 2, 1, 5 ] → next index to flip to is arr.length-2 → array returned from both flips [ 1, 2, 3, 4, 5 ]
• etc. etc. until we’ve touched every value from right to left

Array changes peer iteration:

• [ 1, 5, 4, 3, 2 ] → [ 5, 1, 4, 3, 2 ] → [ 2, 3, 4, 1, 5 ]
• [ 2, 3, 4, 1, 5 ] → [ 4, 3, 2, 1, 5 ] → [ 1, 2, 3, 4, 5 ]
• [ 1, 2, 3, 4, 5 ] → [ 3, 2, 1, 4, 5 ] → [ 1, 2, 3, 4, 5 ]
• continue until i == 0

Hopefully, the above illustration helps clarify the concept behind pancake sorting.

If it didn’t, well maybe some code will help.

So we know we need a function that will flip an array from 0-k.

It could look like this:

This function goes from the outside in, swapping the values at the opposing indices until they meet at the center, which is when the loop would break.

Okay. Now we need a quick and easy way of finding the index of the max value in the array — but only up to a specific index. Remember we want to know the max value excluding the max values we’ve already ordered within the array.

We’ll solve this by creating another helper function that we can pass an array and index to. The function will search for the max value of the array only up to the index we provide.

Awesome. Now that we’ve got this, we just need to write the code for the procedure we discussed earlier!

So we’re looping through the array → on each iteration, we first check to find the maxInd on line 23. Then we use the maxInd and pass it with the array to the flip() function we created. The flip function mutates the array to place the maxVal at the front of the array. We then take the mutated array and pass it back to the flip() function as well as the index we are iterating on (remember starting from the back of the array at i = array.length-1) to flip the maxVal from the front of the array to the end of the array. We do this until we’ve checked every value within the array.

Complexity

With this solution, we have a time complexity of O(n²). Since every iteration requires 2 flips, with each one taking O(n) at most as well as every iteration having to find the maxVal which is also O(n) → resulting in an O(n²) runtime. Since the solution doesn’t initiate more than a few auxiliary variables and we mutate the original array provided to us, this leaves the space complexity to O(1).

Final Thoughts

This one took me a minute to wrap my head around, but once I saw it in action it made a lot of sense. If it isn’t clear how pancake sorting works, try running the code and console logging the array after each mutation. I hope this helps in your next algorithm. Happy hacking!

More content at plainenglish.io