*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #667 (*Medium*): Beautiful Arrangement II

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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.

####
*Examples:*

*Examples:*

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.

####
*Constraints:*

*Constraints:*

- The
`n`

and`k`

are in the range`1 <= k < n <= 10^4`

.

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

For this problem, we have to think about the nature of the range of possible values for **k** and their matching arrays. The smallest value of **k** possible is obviously **1**, which can be achieved by a strictly increasing (or decreasing) array. Thinking about the largest possible value for **k**, however, is slightly more challenging.

First, we can consider the range of values in our array, which is **[1, n]**. The largest possible absolute difference of any two numbers in that range would obviously be the difference between the two extremes, **1** and **n**, which is **n - 1**. Since the smallest possible absolute difference is obviously **1**, then it would appear to perhaps be possible to achieve each difference in the range **[1, n - 1]**, or a **k** value of **n - 1**.

*But is this actually possible?*

Let's take **n = 5** and **k = 4** for example. The only possible way to get the absolute difference of **4** would be for **1** and **5** to be consecutive. After that there are two possibilities for next smallest absolute difference of **3**, which are **1** & **4** or **2** & **5**. Since the **1** and **5** are already next to each other, that means we can achieve this second step with either **[1,5,2]** or **[4,1,5]** (or their reverses).

Continuing this trend along, we can gradually see that we can indeed achieve the maximum **k** value of **n - 1** by zig-zagging back and forth between the remaining extremes as we add them to our array. In the previous example, one such example would be **[1,5,2,4,3]**.

The question then remains how we go about achieving some medium value of **k** larger than **1** but smaller than **n - 1**. The answer to that lies in considering the array to be made of two parts. In the first part, **[1, k+1]**, we can achieve our **k** number of absolute differences, then we can simply fill in the remaining range, **[k+2, n]**, with the ideal incrementing values without increasing the value of **k**.

For example, if we have **n = 8** and **k = 4**, we would build the first part the same as the last example, **[1,5,2,4,3]**, then we would add on the remaining values in increasing order, **[6,7,8]**, to make the wole array, **[1,5,2,4,3,6,7,8]**.

*Examples of each variation of k when n = 8:*

To achieve the zig-zag fill, we can use variables for the top and bottom values of our first part (**a, z**), then use a **modulo** operation (**i % 2**) to alternate between the two options, remembering to increment/decrement the respective variables each time they're used.

A slightly easier to visualize (but harder to code) version of the solution similarly involves using the same zig-zag for the first **k** elements, but with the full range of **n** numbers, and then moving in ideal fashion (either increasing or decreasing by **1**, depending on whether **k** is even or odd) to fill the remaining elements of the array.

*Examples of each alternate variation of k when n = 8:*

####
*Implementation:*

*Implementation:*

The are only minor differences between each of the four languages.

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var constructArray = function(n, k) {
let ans = new Array(n)
for (let i = 0, a = 1, z = k + 1; i <= k; i++)
ans[i] = i % 2 ? z-- : a++
for (let i = k + 1; i < n;)
ans[i] = ++i
return ans
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def constructArray(self, n: int, k: int) -> List[int]:
ans, a, z = [0] * n, 1, k + 1
for i in range(k+1):
if i % 2:
ans[i] = z
z -= 1
else:
ans[i] = a
a += 1
for i in range(k+1,n):
ans[i] = i + 1
return ans
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int[] constructArray(int n, int k) {
int[] ans = new int[n];
for (int i = 0, a = 1, z = k + 1; i <= k; i++)
ans[i] = i % 2 == 1 ? z-- : a++;
for (int i = k+1; i < n;)
ans[i] = ++i;
return ans;
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

## Top comments (0)