# LeetCode 667: Beautiful Arrangement II

## Problem Restatement

We are given two integers:

| Variable | Meaning |
|---|---|
| `n` | We must use numbers from `1` to `n` |
| `k` | Required number of distinct adjacent differences |

We need to construct an array containing every integer from `1` to `n` exactly once such that the set of absolute differences between neighboring elements contains exactly `k` distinct values.

For an array:

```python
arr
```

the adjacent differences are:

```python
|arr[i] - arr[i + 1]|
```

for all valid indices `i`.

Return any valid array.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integers `n` and `k` |
| Output | A permutation of `1` to `n` |
| Distinctness rule | Adjacent absolute differences must contain exactly `k` distinct values |
| Permutation rule | Every number from `1` to `n` appears exactly once |

Example function shape:

```python
def constructArray(n: int, k: int) -> list[int]:
    ...
```

## Examples

Consider:

```python
n = 3
k = 1
```

One valid answer is:

```python
[1, 2, 3]
```

The adjacent differences are:

```text
|1 - 2| = 1
|2 - 3| = 1
```

The distinct difference set is:

```text
{1}
```

So there is exactly one distinct difference.

Now consider:

```python
n = 3
k = 2
```

One valid answer is:

```python
[1, 3, 2]
```

The adjacent differences are:

```text
|1 - 3| = 2
|3 - 2| = 1
```

The distinct difference set is:

```text
{1, 2}
```

So there are exactly two distinct differences.

Another example:

```python
n = 7
k = 3
```

One valid construction is:

```python
[1, 4, 2, 3, 5, 6, 7]
```

The adjacent differences are:

```text
3, 2, 1, 2, 1, 1
```

The distinct set is:

```text
{1, 2, 3}
```

## First Thought: Try All Permutations

A direct solution is to generate every permutation of:

```text
1, 2, ..., n
```

and count the distinct adjacent differences.

This works for very small `n`, but the number of permutations is:

```text
n!
```

which becomes impossible quickly.

We need a direct construction.

## Key Insight

We want exactly:

```text
k distinct differences
```

The important observation is:

```text
Using alternating low and high numbers creates many distinct differences.
```

For example:

```python
1, 5, 2, 4, 3
```

produces differences:

```text
4, 3, 2, 1
```

This creates a decreasing sequence of distinct differences.

More generally, if we alternate between the smallest and largest remaining values, we create new differences step by step.

## Constructing Exactly k Differences

Suppose we want:

```text
k distinct differences
```

We can build the first `k + 1` elements carefully so their differences are:

```text
k, k - 1, k - 2, ..., 1
```

That gives exactly `k` distinct values.

After that, we append the remaining numbers in increasing order.

Those later differences are only:

```text
1
```

which already exists in the set, so no new distinct difference is created.

## Alternating Pattern

Use two pointers:

| Pointer | Meaning |
|---|---|
| `left` | Smallest unused value |
| `right` | Largest value needed for the alternating block |

Build the first `k + 1` numbers by alternating:

```text
smallest, largest, next smallest, next largest, ...
```

This generates distinct differences:

```text
k, k - 1, k - 2, ...
```

Then append the remaining values in increasing order.

## Example Walkthrough

Suppose:

```python
n = 7
k = 3
```

We use numbers:

```text
1 to 4
```

for the alternating section.

Start:

```text
left = 1
right = 4
```

Build:

```text
1, 4, 2, 3
```

Differences:

```text
3, 2, 1
```

Exactly three distinct values.

Now append the remaining numbers:

```text
5, 6, 7
```

Final array:

```python
[1, 4, 2, 3, 5, 6, 7]
```

The later differences are only `1` or `2`, which are already present.

## Algorithm

1. Create an empty result list.
2. Set:
   - `left = 1`
   - `right = k + 1`
3. Alternate between `left` and `right`:
   - Append `left`, increase `left`
   - Append `right`, decrease `right`
4. Continue until all values from `1` to `k + 1` are used.
5. Append remaining values:
   - `k + 2` to `n`
6. Return the result.

## Correctness

The alternating construction uses exactly the numbers from `1` to `k + 1`.

At every step, the difference between consecutive elements decreases by `1`.

For example:

```text
1, k+1, 2, k, 3, ...
```

creates differences:

```text
k, k-1, k-2, ...
```

Therefore, the first `k` adjacent differences are all distinct and equal to:

```text
1, 2, ..., k
```

So the array already contains exactly `k` distinct differences.

The remaining values are appended in increasing order. Their adjacent differences are all `1`, which is already included in the existing difference set. Therefore, no new distinct differences are introduced.

Every number from `1` to `n` appears exactly once, so the result is a valid permutation.

Thus, the algorithm constructs a permutation whose adjacent differences contain exactly `k` distinct values.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Every number is appended once |
| Space | `O(n)` | The output array stores `n` numbers |

## Implementation

```python
from typing import List

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        result = []

        left = 1
        right = k + 1

        while left <= right:
            result.append(left)
            left += 1

            if left <= right:
                result.append(right)
                right -= 1

        for value in range(k + 2, n + 1):
            result.append(value)

        return result
```

## Code Explanation

We begin with:

```python
left = 1
right = k + 1
```

The alternating section uses numbers from:

```text
1 to k + 1
```

Then we alternate between the smallest and largest remaining values:

```python
result.append(left)
left += 1
```

and:

```python
result.append(right)
right -= 1
```

This creates decreasing distinct differences.

For example:

```text
1, 5, 2, 4, 3
```

produces:

```text
4, 3, 2, 1
```

After all numbers in the alternating block are used, we append the remaining numbers normally:

```python
for value in range(k + 2, n + 1):
    result.append(value)
```

These only create differences already present.

Finally:

```python
return result
```

returns the constructed permutation.

## Testing

```python
def distinct_differences(arr):
    return len({
        abs(arr[i] - arr[i + 1])
        for i in range(len(arr) - 1)
    })

def run_tests():
    s = Solution()

    arr = s.constructArray(3, 1)
    assert sorted(arr) == [1, 2, 3]
    assert distinct_differences(arr) == 1

    arr = s.constructArray(3, 2)
    assert sorted(arr) == [1, 2, 3]
    assert distinct_differences(arr) == 2

    arr = s.constructArray(7, 3)
    assert sorted(arr) == [1, 2, 3, 4, 5, 6, 7]
    assert distinct_differences(arr) == 3

    arr = s.constructArray(10, 4)
    assert sorted(arr) == list(range(1, 11))
    assert distinct_differences(arr) == 4

    arr = s.constructArray(2, 1)
    assert sorted(arr) == [1, 2]
    assert distinct_differences(arr) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n=3, k=1` | Smallest simple case |
| `n=3, k=2` | Maximum distinct differences for size `3` |
| `n=7, k=3` | Standard alternating construction |
| `n=10, k=4` | Larger example |
| `n=2, k=1` | Smallest valid input |