Sponsored
Sponsored
This approach involves sorting the array by repeatedly moving the largest unsorted element to its correct position at the end. This is achieved by two flips: first flipping the array to get the largest element to the front, and then flipping up to the end of the unsorted part to push the largest element to the end.
Time Complexity: O(n^2) due to nested loops finding the maximum index and reversing. Space Complexity: O(1) due to in-place operations.
1function pancakeSort(arr) {
2 let res = [];
3 for (let cur_len = arr.length; cur_len > 1; cur_len--) {
4 let max_idx = 0;
5 for (let i = 0; i < cur_len; i++) {
6 if (arr[i] > arr[max_idx]) max_idx = i;
7 }
8 if (max_idx !== cur_len - 1) {
9 if (max_idx !== 0) {
10 arr = arr.slice(0, max_idx + 1).reverse().concat(arr.slice(max_idx + 1));
11 res.push(max_idx + 1);
12 }
13 arr = arr.slice(0, cur_len).reverse().concat(arr.slice(cur_len));
14 res.push(cur_len);
15 }
16 }
17 return res;
18}
19
20const arr = [3, 2, 4, 1];
21console.log(pancakeSort(arr));JavaScript uses array slicing and concatenation to handle subarray reversals, progressing through the array to sort it while tracking the k-values for each flip.