101 Logo
onenoughtone

Code Implementation

Pancake Sorting Implementation

Below is the implementation of the pancake sorting:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Optimized Greedy Approach
 * Time Complexity: O(n²) - For each position, we need to find the element and perform flips
 * Space Complexity: O(n) - We need space to store the result array
 *
 * @param {number[]} arr - The array to be sorted
 * @return {number[]} - The sequence of k values for pancake flips
 */
function pancakeSort(arr) {
  const n = arr.length;
  const result = [];
 
  // Helper function to reverse the first k elements of the array
  function flip(k) {
    let left = 0;
    let right = k - 1;
    while (left < right) {
      // Swap elements at left and right indices
      const temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    }
  }
 
  // Sort the array one element at a time, starting from the largest
  for (let i = n - 1; i > 0; i--) {
    // Find the index of the element with value i+1
    let j = 0;
    while (j <= i && arr[j] !== i + 1) {
      j++;
    }
 
    // If the element is already in the correct position, skip
    if (j === i) {
      continue;
    }
 
    // Move the element to the beginning of the array
    if (j > 0) {
      result.push(j + 1);
      flip(j + 1);
    }
 
    // Move the element to its correct position
    result.push(i + 1);
    flip(i + 1);
  }
 
  return result;
}

Step-by-Step Explanation

Let's break down the implementation:

  1. 1. Understand the Problem: First, understand that we need to sort an array using only pancake flips, where a pancake flip reverses the first k elements of the array.
  2. 2. Implement the Flip Operation: Create a helper function to perform a pancake flip, which reverses the first k elements of the array.
  3. 3. Sort from Largest to Smallest: Sort the array one element at a time, starting from the largest element and working down to the smallest.
  4. 4. Find Each Element: For each position, find the index of the element that should be in that position.
  5. 5. Move Elements to Their Correct Positions: Use two pancake flips to move each element to its correct position: first flip to bring the element to the beginning, then flip to move it to its correct position.
  6. 6. Track Flip Operations: Keep track of the k values used in each pancake flip and return them as the result.
  7. 7. Handle Edge Cases: Handle edge cases such as when an element is already in its correct position.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone