Leetcode 969. Pancake Sorting
Problem Explanation
Given an unsorted array, you are allowed to reverse the order of the first k
elements (k
<= number of elements in the array) of the array, and this operation is known as a pancake flip. You have to sort this array using the above operation and return the k
values.
Let's take an example: If the array is [3, 2, 4, 1]. The sequence of pancake flips is [4, 2, 4, 3]. The array can be sorted from highest to lowest using these steps:
Original array: [3, 2, 4, 1]
After 1st flip (k=4): [1, 4, 2, 3]
After 2nd flip (k=2): [4, 1, 2, 3]
After 3rd flip (k=4): [3, 2, 1, 4]
After 4th flip (k=3): [1, 2, 3, 4] -> This is sorted array.
For each unplaced element from the largest target
to the smallest 1, there are two steps to put target
at its final position:
- Locate the position
i
oftarget
and do a pancake flip ati + 1
to movetarget
to the beginning. - Then do a pancake flip at
target
to movetarget
to its final position.
Solution in Python
1 2python 3class Solution: 4 def pancakeSort(self, arr): 5 ans = [] 6 7 for target in range(len(arr), 0, -1): 8 i = arr.index(target) 9 arr[:i+1] = reversed(arr[:i+1]) 10 arr[:target] = reversed(arr[:target]) 11 ans += [i+1, target] 12 13 return ans
Solution in Java
1 2java 3class Solution { 4 public List<Integer> pancakeSort(int[] arr) { 5 List<Integer> ans = new ArrayList(); 6 7 for (int target = arr.length; target > 0; target--) { 8 int i; 9 for (i = 0; arr[i] != target; i++); 10 reverse(arr, i + 1); 11 reverse(arr, target); 12 ans.add(i + 1); 13 ans.add(target); 14 } 15 16 return ans; 17 } 18 19 public void reverse(int[] arr, int k) { 20 for (int i = 0, j = k - 1; i < j; i++, j--) { 21 int tmp = arr[i]; 22 arr[i] = arr[j]; 23 arr[j] = tmp; 24 } 25 } 26}
Solution in Javascript
1 2javascript 3var pancakeSort = function(arr) { 4 const res = []; 5 6 for(let target = arr.length; target > 0; target--) { 7 let i; 8 for(i = 0; arr[i] !== target; i++); 9 reverse(arr, 0, i); 10 reverse(arr, 0, target - 1); 11 res.push(i + 1); 12 res.push(target); 13 } 14 15 return res; 16}; 17 18function reverse(arr, i, j) { 19 while(i < j) { 20 const temp = arr[i]; 21 arr[i] = arr[j]; 22 arr[j] = temp; 23 i++; 24 j--; 25 } 26};
Solution in C++
1
2c++
3class Solution {
4public:
5 vector<int> pancakeSort(vector<int>& arr) {
6 vector<int> ans;
7
8 for (int target = arr.size(); target > 0; --target) {
9 auto it = find(arr.begin(), arr.end(), target);
10 reverse(arr.begin(), it + 1);
11 ans.push_back(distance(arr.begin(), it + 1));
12 reverse(arr.begin(), arr.begin() + target);
13 ans.push_back(target);
14 }
15
16 return ans;
17 }
18};
Solution in C#
1 2c# 3public class Solution { 4 public IList<int> PancakeSort(int[] arr) { 5 var ans = new List<int>(); 6 7 for (int target = arr.Length; target > 0; target--) { 8 int i = Array.IndexOf(arr, target); 9 reverse(arr, i + 1); 10 reverse(arr, target); 11 ans.Add(i + 1); 12 ans.Add(target); 13 } 14 15 return ans; 16 } 17 18 private void reverse(int[] arr, int k) { 19 for (int i = 0, j = k - 1; i < j; i++, j--) { 20 var tmp = arr[i]; 21 arr[i] = arr[j]; 22 arr[j] = tmp; 23 } 24 } 25}
A helpful point to remember is that the algorithm doesn't work by placing the smallest elements first but by placing the largest elements at their correct places as early as possible. In practice, this saves a lot of unnecessary operations because once a big number is in its place, it doesn't move anymore.# Solution in Ruby
Here's another solution implemented in Ruby for the same problem. The Array#index
method in Ruby returns the index of the first element that matches the one provided.
1 2ruby 3def pancake_sort(arr) 4 ans = [] 5 6 for target in (arr.length).downto(1) 7 i = arr.index(target) 8 arr[0..i] = arr[0..i].reverse 9 arr[0...target] = arr[0...target].reverse 10 ans += [i+1, target] 11 end 12 13 ans 14end
This Ruby method works by first finding the target value in the array, then reversing the first i+1
elements to bring the target to the start of the array. It then reverses the first i
elements to bring the target to its final position. This process is repeated until all the elements of the array are sorted in ascending order.
The solutions presented above should have given you a good understanding of how to solve this problem in multiple languages. Remember that you can play around with the code to get a better understanding of how it works. The most important part is to have the logic of the problem clear in your mind. Once you have that, implementing the solution becomes a lot simpler.
Remember, practice is the key to mastering any programming language. So try to work on as many coding problems as you can in the language you are comfortable with and then slowly try implementing the same solutions in other languages to increase your skill-set. Happy coding!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.