667. Beautiful Arrangement II #

Problem #

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement:Suppose this list is [a1, a2, a3, … , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] has exactly k distinct integers.

If there are multiple answers, print any of them.

Example 1:

Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.

Example 2:

Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

Note:

The n and k are in the range 1 <= k < n <= 10^4.

Problem Summary #

Given two integers n and k, you need to implement an array that contains n different integers from 1 to n, while satisfying the following conditions:

If this array is [a1, a2, a3, … , an], then the array [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] should have exactly k distinct integers;.
If there are multiple answers, you only need to implement and return any one of them.

Solution Approach #

First consider the case where k takes its maximum value. If the larger values at the end are inserted one by one among the smaller values at the front, forming [1, n, 2, n-1, 3, n-2, ...], then this arrangement allows k to reach its maximum value n-1. The case where k takes its minimum value is [1, 2, 3, 4, ..., n], where the minimum value of k is 1. So how should we arrange the numbers when k takes a value between [1, n-1]? First arrange [1, 2, 3, 4, ..., n-k-1] in order. There are n-k-1 numbers here, which can form exactly one kind of difference. The remaining k+1 numbers form k-1 kinds of differences.
This goes back to the way to achieve the maximum value of k. The case where k takes its maximum value is n numbers forming n-1 different kinds of differences. Now there are k+1 numbers, and they need to form k different kinds of differences. The two are the same problem. Therefore, the arrangement method for the remaining k numbers is [n-k, n-k+1, ..., n]. There are k numbers here. Note that in the code implementation, pay attention to the parity of k: if k is odd, after “interleaving by halves”, they are matched exactly; if k is even, the middle number n-k+(k+1)/2 still needs to be added separately to the arrangement at the end.
Some readers may ask: the front part generated 1 kind of difference, and this latter part generated k kinds of differences, so doesn’t that add up to k + 1 kinds of differences? This understanding is incorrect. The last 2 numbers in the latter segment are n-k+(k+1)/2-1 and n-k+(k+1)/2; the difference between them is 1, which is the same as the difference in the arrangement constructed in the first segment: both are 1. Therefore, the first segment constructs 1 kind of difference, and although the second segment constructs k kinds, the duplicate difference 1 between the two segments must be removed, so the final number of difference types is still 1 + k - 1 = k.

Code #

package leetcode

func constructArray(n int, k int) []int {
	res := []int{}
	for i := 0; i < n-k-1; i++ {
		res = append(res, i+1)
	}
	for i := n - k; i < n-k+(k+1)/2; i++ {
		res = append(res, i)
		res = append(res, 2*n-k-i)
	}
	if k%2 == 0 {
		res = append(res, n-k+(k+1)/2)
	}
	return res
}