969. Pancake Sorting #

Problem #

Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k=4): A = [1, 4, 2, 3]
After 2nd flip (k=2): A = [4, 1, 2, 3]
After 3rd flip (k=4): A = [3, 2, 1, 4]
After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted. 

Example 2:

Input: [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Note:

• 1 <= A.length <= 100
• A[i] is a permutation of [1, 2, …, A.length]

Problem Summary #

Given an array, output the steps of “pancake sorting” so that the final array is sorted in ascending order. In “pancake sorting”, each sorting operation reverses the first n numbers, where n is less than the length of the array.

Solution Approach #

The idea for this problem is to find the largest value in the current unsorted segment of the array each time (initially, the entire array is considered the unsorted segment), and perform a “pancake sort” on the index i of the largest value, reversing the first i elements. This brings the largest value to the first position. Then immediately perform another “pancake sort” of length n, the total length of the array, with the goal of moving the largest value to the last position of the array, so its position is finalized. Then the unsorted segment of the array becomes n-1. Continue looping with this method until every element in the array has reached its final sorted index. The final array will then be sorted.

A special point in this problem is that the elements in the array are all natural integers, so after the final array is sorted, the length of the array is the maximum value. Therefore, there is no need to traverse the array once to find the maximum value; simply taking the length gives the maximum value.

Code #

package leetcode

func pancakeSort(A []int) []int {
	if len(A) == 0 {
		return []int{}
	}
	right := len(A)
	var (
		ans []int
	)
	for right > 0 {
		idx := find(A, right)
		if idx != right-1 {
			reverse969(A, 0, idx)
			reverse969(A, 0, right-1)
			ans = append(ans, idx+1, right)
		}
		right--
	}

	return ans
}

func reverse969(nums []int, l, r int) {
	for l < r {
		nums[l], nums[r] = nums[r], nums[l]
		l++
		r--
	}
}

func find(nums []int, t int) int {
	for i, num := range nums {
		if num == t {
			return i
		}
	}
	return -1
}