> For the complete documentation index, see [llms.txt](https://twchen.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://twchen.gitbook.io/leetcode/array/beautiful-arrangement-ii.md).

# Beautiful Arrangement II

## Description

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:**<br>

```
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:**<br>

```
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:**

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

## Solutions

### My solution

Idea: place `k` numbers in an alternating way: `[1, n, 2, n-1, 3, n-2, ...]`, so there are `k - 1` distinct absolute differences. Then place the remaining numbers in increasing or decreasing order. That is, the last distinct absolute difference is `1`.

```cpp
class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ans(n);
        for(int i = 0; i < k / 2; ++i){
            ans[2 * i] = i + 1;
            ans[2 * i + 1] = n - i;
        }
        int diff, start;
        if(k % 2){
            diff = 1;
            start = k / 2 + 1;
        }else{
            diff = -1;
            start = n - k / 2;
        }
        for(int i = k / 2 * 2; i < n; ++i){
            ans[i] = start;
            start += diff;
        }
        return ans;
    }
};
```

### A better solution

Idea: put first `k + 1` numbers in the order `[1, k+1, 2, k, 3, ...]`, which forms k distinct distances `[k, k-1, ..., 1]`. Let's say this is the first part. Then the second part is formed by putting the remaining numbers in increasing order. Note the distance between the last element of the first part and first element of the second part is in `[k, k-1, ..., 1]`. And adding the second part will not produce a new distance.

Reference: <https://leetcode.com/problems/beautiful-arrangement-ii/discuss/106957/C++-concise-code-O(n)>

```cpp
class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ans(n);
        int s = 1, l = k + 1;
        for(int i = 0; i < k + 1; ++i){
            ans[i] = i % 2 ? l-- : s++;
        }
        for(int i = k + 1; i < n; ++i){
            ans[i] = i + 1;
        }
        return ans;
    }
};
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://twchen.gitbook.io/leetcode/array/beautiful-arrangement-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.