> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/601-700/beautiful-arrangement-ii.md).

# 667. 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.

### Constraints

1. The `n` and `k` are in the range 1 <= k < n <= 104.

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/beautiful-arrangement-ii/)
* ProgramCreek
* [YouTube](https://youtu.be/BiQlqgmJ0BM)

### **Examples**

{% tabs %}
{% tab title="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.
{% endtab %}

{% tab title="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.
{% endtab %}

{% tab title="Example 3" %}
**Input:** n = 9, k = 6

**Output:** \[1, 9, 2, 8, 3, 7, 6, 5, 4]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */

class Solution {
    public int[] constructArray(int n, int k) {
        int[] result = new int[n];
        
        int low = 1, high = n;
        int index = 0;
        
        result[index++] = low++;
        boolean isHigh = false;
        
        while(k > 1) {
            result[index++] = high--;
            k--;
            isHigh = true;
            if(k > 1) {
                result[index++] = low++;
                k--;
                isHigh = false;
            }
        }
        
        while(index < n) {
            if(isHigh) {
                result[index++] = high--;
            } else {
                result[index++] = low++;
            }
        }
        
        return result;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*