> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Beautiful Arrangement II Python Solution

> Tested Python solution for LeetCode 667 with 19 pytest cases. Generate a practice environment with lcpy.

LeetCode 667, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Math](/catalog/topics/math). [View on LeetCode](https://leetcode.com/problems/beautiful-arrangement-ii/description/).

Generate this problem as a practice environment: tested reference solution, 19 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 667   # by problem number
lcpy gen -s beautiful_arrangement_ii   # by problem name
```

## Problem

Given two integers `n` and `k`, construct a list `answer` that contains `n` different positive integers ranging from `1` to `n` and obeys the following requirement:

* Suppose this list is `answer = [a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, ..., a<sub>n</sub>]`, then the list `[|a<sub>1</sub> - a<sub>2</sub>|, |a<sub>2</sub> - a<sub>3</sub>|, |a<sub>3</sub> - a<sub>4</sub>|, ..., |a<sub>n-1</sub> - a<sub>n</sub>|]` has exactly `k` distinct integers.

Return *the list* `answer`. If there are multiple valid answers, return **any of them**.

### Examples

```
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.
```

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

* `1 <= k < n <= 10^4`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/beautiful_arrangement_ii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/beautiful_arrangement_ii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Zig-zag the first k+1 values between the low and high ends: the k gaps of that
    # prefix are exactly k, k-1, ..., 1, then a plain ascending run keeps only 1.
    # Time: O(n)
    # Space: O(1) extra besides the output list
    def construct_array(self, n: int, k: int) -> list[int]:
        result: list[int] = []
        low, high = 1, k + 1
        while low < high:
            result.extend([low, high])
            low += 1
            high -= 1
        if low == high:
            result.append(low)
        result.extend(range(k + 2, n + 1))
        return result
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(1) extra besides the output list |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.