Solution: Beautiful Arrangement II
Tags: algorithms, javascript, java, python
Published: 2021-04-12 09:20:40

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/beautiful-arrangement-ii/discuss/1154742).*

---

#### [Leetcode Problem #667 (*Medium*): Beautiful Arrangement II](https://leetcode.com/problems/beautiful-arrangement-ii/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:***
>
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:***
>
 - The `n` and `k` are in the range `1 <= k < n <= 10^4`.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

![Visual 1](https://i.imgur.com/OOuahhe.png)

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

![Visual 2](https://i.imgur.com/foIzoFT.png)

---

#### ***Implementation:***

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

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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;
    }
};
```