Code Implementation

class Solution:
    def constructArray(self, n: int, k: int) -> list[int]:
        answer = []
        left, right = 1, n
        for i in range(k):
            if i % 2 == 0:
                answer.append(left)
                left += 1
            else:
                answer.append(right)
                right -= 1
        # Fill the rest in order
        if k % 2 == 0:
            answer.extend(range(right, left - 1, -1))
        else:
            answer.extend(range(left, right + 1))
        return answer
      

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> answer;
        int left = 1, right = n;
        for (int i = 0; i < k; ++i) {
            if (i % 2 == 0) {
                answer.push_back(left++);
            } else {
                answer.push_back(right--);
            }
        }
        if (k % 2 == 0) {
            for (int i = right; i >= left; --i)
                answer.push_back(i);
        } else {
            for (int i = left; i <= right; ++i)
                answer.push_back(i);
        }
        return answer;
    }
};
      

class Solution {
    public int[] constructArray(int n, int k) {
        int[] answer = new int[n];
        int left = 1, right = n;
        int idx = 0;
        for (int i = 0; i < k; ++i) {
            if (i % 2 == 0) {
                answer[idx++] = left++;
            } else {
                answer[idx++] = right--;
            }
        }
        if (k % 2 == 0) {
            for (int i = right; i >= left; --i) {
                answer[idx++] = i;
            }
        } else {
            for (int i = left; i <= right; ++i) {
                answer[idx++] = i;
            }
        }
        return answer;
    }
}
      

var constructArray = function(n, k) {
    let answer = [];
    let left = 1, right = n;
    for (let i = 0; i < k; ++i) {
        if (i % 2 === 0) {
            answer.push(left++);
        } else {
            answer.push(right--);
        }
    }
    if (k % 2 === 0) {
        for (let i = right; i >= left; --i) {
            answer.push(i);
        }
    } else {
        for (let i = left; i <= right; ++i) {
            answer.push(i);
        }
    }
    return answer;
};
      

Problem Description

Given two integers n and k, construct an array answer of length n such that:

• It contains all integers from 1 to n exactly once (no repeats).
• The list of absolute differences between consecutive elements has exactly k distinct values.

Thought Process

At first glance, the problem seems to ask for a specific arrangement of numbers with a complex difference pattern. A brute-force approach would be to try all permutations, but this is computationally infeasible for large n.

The key insight is to recognize that we can control the number of distinct differences by carefully alternating between the smallest and largest available numbers. This creates large and small jumps, maximizing the number of distinct differences early, and then we can fill in the rest in order to avoid introducing new differences.

Solution Approach

Here's how we can efficiently construct such an array:

1. Initialization: Start with two pointers: left = 1 and right = n.
2. Alternating Selection: For the first k positions, alternate picking from the left and right pointers:
   • If the index is even, pick from left and increment it.
   • If the index is odd, pick from right and decrement it.
   This ensures that each new difference is unique, leading to exactly k distinct differences.
3. Filling the Rest: After k steps, fill the remaining positions with the numbers left, in order (either ascending or descending, depending on the parity of k), to avoid introducing new differences.
4. Result: The constructed array meets the condition of k distinct differences.

This approach is efficient and guarantees a valid solution.

Example Walkthrough

Let's walk through the process with n = 7 and k = 3:

1. Start: left = 1, right = 7, answer = []
2. For i = 0 (even): pick 1 (left), increment left to 2.
   answer: [1]
3. For i = 1 (odd): pick 7 (right), decrement right to 6.
   answer: [1, 7]
4. For i = 2 (even): pick 2 (left), increment left to 3.
   answer: [1, 7, 2]
5. Now, k = 3 steps are done. Remaining numbers: 3, 4, 5, 6.
6. Since k is odd, fill in order from left to right: 3, 4, 5, 6.
   Final answer: [1, 7, 2, 3, 4, 5, 6]
7. The absolute differences are: |1-7|=6, |7-2|=5, |2-3|=1, |3-4|=1, |4-5|=1, |5-6|=1
   The distinct differences: 1, 5, 6 → exactly 3 distinct values.

Time and Space Complexity

• Brute-force approach: Would require generating all permutations of n numbers, which is O(n!) time and space. This is not feasible for large n.
• Optimized approach (above): We only loop through n elements once, so the time complexity is O(n). We use an array of size n for the answer, so space complexity is also O(n).

Summary

The Beautiful Arrangement II problem can be solved elegantly by alternating between picking the smallest and largest available numbers for the first k steps, then filling in the rest in order. This guarantees exactly k distinct adjacent differences, meets the constraints, and is highly efficient. The key insight is realizing how alternating selections maximize difference diversity, and that the rest can be filled without introducing new differences.