Skip to content

969. Pancake Sorting 👎

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  vector<int> pancakeSort(vector<int>& arr) {
    vector<int> ans;

    for (int target = arr.size(); target >= 1; --target) {
      int index = find(arr, target);
      reverse(arr.begin(), arr.begin() + index + 1);
      reverse(arr.begin(), arr.begin() + target);
      ans.push_back(index + 1);
      ans.push_back(target);
    }

    return ans;
  }

 private:
  int find(vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); ++i)
      if (arr[i] == target)
        return i;
    throw;
  }
};

 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
class Solution {
  public List<Integer> pancakeSort(int[] arr) {
    List<Integer> ans = new ArrayList<>();

    for (int target = arr.length; target >= 1; --target) {
      int index = find(arr, target);
      reverse(arr, 0, index);
      reverse(arr, 0, target - 1);
      ans.add(index + 1);
      ans.add(target);
    }

    return ans;
  }

  private int find(int[] arr, int target) {
    for (int i = 0; i < arr.length; ++i)
      if (arr[i] == target)
        return i;
    throw new IllegalArgumentException();
  }

  private void reverse(int[] arr, int l, int r) {
    while (l < r)
      swap(arr, l++, r--);
  }

  private void swap(int[] arr, int l, int r) {
    int temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def pancakeSort(self, arr: List[int]) -> List[int]:
    ans = []

    for target in range(len(arr), 0, -1):
      index = arr.index(target)
      arr[:index + 1] = arr[:index + 1][::-1]
      arr[:target] = arr[:target][::-1]
      ans.append(index + 1)
      ans.append(target)

    return ans