# Beautiful Arrangement II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/beautiful-arrangement-ii)
Canonical: https://scaleengineer.com/dsa/problems/beautiful-arrangement-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## 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 = [a1, a2, a3, ... , an]`, then the list `[|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|]` has exactly `k` distinct integers.

Return _the list_ `answer`. If there multiple valid answers, return **any of them**.

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

* `1 <= k < n <= 104`

# Approaches
## Brute-Force with Permutations
This approach involves generating every possible arrangement (permutation) of numbers from 1 to `n`. For each permutation, we calculate the absolute differences between adjacent elements and count the number of unique differences. If the count matches `k`, we have found a valid arrangement and can return it.
**Time:** O(n! * n). There are `n!` permutations of `n` numbers. For each permutation, we perform `n-1` calculations to find the differences, taking O(n) time. This complexity makes the approach infeasible for the given constraints. · **Space:** O(n). This space is used to store a single permutation, the set of differences, and for the recursion stack if generating permutations recursively.
**Pros:** Conceptually simple and easy to understand.; Guaranteed to find a solution.
**Cons:** Extremely inefficient due to factorial time complexity.; Will result in a 'Time Limit Exceeded' error on any platform for `n` greater than about 10 or 11.
### Explanation
The most straightforward but naive way to solve the problem is to explore every single possibility. The set of all possible arrangements of `n` distinct numbers is the set of all permutations. We can generate each permutation of the numbers `[1, 2, ..., n]` and, for each one, verify if it meets the condition. To verify a permutation `[a₁, a₂, ..., aₙ]`, we compute the differences `|a₁ - a₂|, |a₂ - a₃|, ..., |aₙ₋₁ - aₙ|` and count how many of them are distinct. A `HashSet` is suitable for this counting. If the count equals `k`, we have found our answer. Since the problem guarantees that a solution exists, this method will eventually find one.
### Algorithm
1. Generate all `n!` permutations of numbers from `1` to `n`.
2. For each permutation, do the following:
   a. Create an empty set to store the distinct differences.
   b. Iterate through the permutation from the first to the second-to-last element.
   c. Calculate the absolute difference between the current element and the next element.
   d. Add the calculated difference to the set.
3. After iterating through the permutation, check if the size of the set is equal to `k`.
4. If it is, the current permutation is a valid solution. Return it.
5. If no solution is found after checking all permutations (which is impossible based on the problem statement), return null.

## Backtracking with Pruning
This is an improvement over the brute-force approach. Instead of generating a full permutation and then checking it, we build the arrangement one number at a time. We maintain a set of used numbers and a set of differences encountered so far. If at any point the number of distinct differences exceeds `k`, we prune that search path and backtrack.
**Time:** O(k^n) or similar exponential complexity in the worst case. While better than O(n!), it is not efficient enough for the given constraints. · **Space:** O(n) for the recursion stack, the list storing the current path, and the boolean `used` array.
**Pros:** More efficient than pure brute-force due to pruning.; It is a general strategy for solving constraint satisfaction problems.
**Cons:** Still has a worst-case exponential time complexity.; Too slow for the given constraints (`n` up to 10^4), leading to 'Time Limit Exceeded'.; The pruning logic can be tricky to implement effectively.
### Explanation
Backtracking systematically builds a candidate solution and abandons it as soon as it determines that it cannot be completed to a valid solution. We build the list of numbers one by one. At each step, we try to place an unused number. After placing a number, we check the new set of differences. If the number of distinct differences already exceeds `k`, we know this path cannot lead to a solution, so we 'prune' it by not exploring it further. This is more efficient than generating the full permutation because we discard invalid partial solutions early. However, the search space can still be very large, making this approach too slow for the problem's constraints.

```java
class Solution {
    int[] ans;
    boolean[] used;
    int n, k;

    public int[] constructArray(int n, int k) {
        this.n = n;
        this.k = k;
        this.used = new boolean[n + 1];
        List<Integer> path = new ArrayList<>();
        solve(path);
        return ans;
    }

    private boolean solve(List<Integer> path) {
        if (path.size() == n) {
            Set<Integer> diffs = new HashSet<>();
            for (int i = 0; i < n - 1; i++) {
                diffs.add(Math.abs(path.get(i) - path.get(i + 1)));
            }
            if (diffs.size() == k) {
                ans = path.stream().mapToInt(Integer::intValue).toArray();
                return true;
            }
            return false;
        }

        // Pruning check
        Set<Integer> currentDiffs = new HashSet<>();
        for (int i = 0; i < path.size() - 1; i++) {
            currentDiffs.add(Math.abs(path.get(i) - path.get(i + 1)));
        }
        if (currentDiffs.size() > k) {
            return false;
        }

        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.add(i);
                if (solve(path)) {
                    return true;
                }
                path.remove(path.size() - 1); // Backtrack
                used[i] = false;
            }
        }
        return false;
    }
}
```
### Algorithm
1. Define a recursive function, e.g., `solve(path)`, where `path` is the list being constructed.
2. The base case for the recursion is when `path.size() == n`. At this point, check if the number of distinct differences is exactly `k`. If so, a solution is found.
3. In the recursive step, iterate through all numbers from `1` to `n`.
4. For each number `num` not yet used in the `path`:
   a. Add `num` to the `path`.
   b. Mark `num` as used.
   c. **Pruning**: Before the recursive call, calculate the set of distinct differences for the current `path`. If the size of this set exceeds `k`, this path is invalid, so we backtrack immediately.
   d. Make a recursive call: `solve(path)`.
   e. If the recursive call finds a solution, propagate it upwards.
   f. **Backtrack**: Remove `num` from the `path` and unmark it as used to explore other possibilities.

## Optimal Constructive Approach
This optimal approach directly constructs a valid array in linear time. The key insight is to combine two simple patterns: one that generates many distinct differences and one that generates only one distinct difference. By creating a prefix that generates `k` distinct differences and then appending the rest of the numbers in a simple sequence (which only generates differences of 1), we can achieve the desired result.
**Time:** O(n), as we iterate through the numbers from 1 to `n` once to fill the result array. · **Space:** O(1) extra space. The O(n) space for the result array is not typically counted as extra space.
**Pros:** Optimal O(n) time complexity.; Optimal O(1) extra space complexity (excluding the output array).; Simple to implement once the pattern is understood.; Directly builds the solution without any searching or backtracking.
**Cons:** The underlying logic for why this construction works might not be immediately obvious.
### Explanation
We can construct the array by observing patterns for the minimum and maximum possible values of `k`.
- For `k=1`, the array `[1, 2, 3, ..., n]` works, giving only the difference `1`.
- For maximum `k`, the array `[1, n, 2, n-1, ...]` generates a wide range of differences.

We can combine these ideas. To get exactly `k` distinct differences, we can construct the first part of the array to produce `k` distinct differences, and the rest of the array to produce no new differences. A clever way to generate `k` distinct differences (`k, k-1, ..., 1`) is to arrange the first `k+1` numbers as `[1, k+1, 2, k, 3, ...]`. This prefix uses numbers from `1` to `k+1`.

After this prefix is constructed, we can simply append the remaining numbers, `k+2, k+3, ..., n`, in increasing order. The differences in this latter part will all be `1`, which is a difference we have already created in the prefix. The single difference between the end of the prefix and the start of the suffix will not violate the `k` distinct difference count. This method guarantees a valid construction in a single pass.

```java
class Solution {
    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        int idx = 0;
        int low = 1, high = k + 1;
        
        // Construct the first k+1 elements to generate k distinct differences.
        // This part creates differences: k, k-1, k-2, ..., 1.
        while (low <= high) {
            ans[idx++] = low++;
            if (low <= high) {
                ans[idx++] = high--;
            }
        }
        
        // Append the rest of the numbers. These will have a difference of 1.
        // The numbers from k+2 to n are simply appended in order.
        for (int i = k + 2; i <= n; i++) {
            ans[idx++] = i;
        }
        
        return ans;
    }
}
```
### Algorithm
1. Create an integer array `ans` of size `n`.
2. Initialize two pointers, `low = 1` and `high = k + 1`.
3. Initialize an index for the `ans` array, `idx = 0`.
4. Construct the first `k + 1` elements of `ans` by alternating between `low` and `high` to generate `k` distinct differences (`k, k-1, ..., 1`).
   - In a loop that runs as long as `low <= high`:
     a. Place `low` into `ans` and increment `low`: `ans[idx++] = low++`.
     b. If `low` has not surpassed `high`, place `high` into `ans` and decrement `high`: `ans[idx++] = high--`.
5. The first `k + 1` elements are now set. The numbers used are `1` through `k + 1`.
6. Fill the rest of the array (`idx` from `k + 1` to `n - 1`) with the remaining numbers (`k + 2, k + 3, ..., n`) in simple increasing order.
   - For `i` from `k + 2` to `n`, set `ans[idx++] = i`.
7. Return the constructed array `ans`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

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

```