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.
1def pancakeSort(arr):
2 res = []
3 cur_len = len(arr)
4 while cur_len > 1:
5 max_idx = arr.index(max(arr[:cur_len]))
6 if max_idx != cur_len - 1:
7 if max_idx != 0:
8 arr[:max_idx + 1] = arr[:max_idx + 1][::-1]
9 res.append(max_idx + 1)
10 arr[:cur_len] = arr[:cur_len][::-1]
11 res.append(cur_len)
12 cur_len -= 1
13 return res
14
15arr = [3, 2, 4, 1]
16print(pancakeSort(arr))This Python solution uses list slicing to flip subarrays efficiently, and it appends the corresponding k-values to the result list as required.