Beautiful Arrangement II
Problem
Construct any permutation of 1..n whose adjacent-difference set has exactly k distinct values.
n=3 k=2[1,3,2]def construct_array(n, k):
out = []; lo, hi = 1, k + 1
while lo <= hi:
out.append(lo); lo += 1
if lo <= hi: out.append(hi); hi -= 1
for v in range(k + 2, n + 1): out.append(v)
return outfunction constructArray(n, k) {
const out = []; let lo = 1, hi = k + 1;
while (lo <= hi) { out.push(lo++); if (lo <= hi) out.push(hi--); }
for (let v = k + 2; v <= n; v++) out.push(v);
return out;
}int[] constructArray(int n, int k) {
int[] out = new int[n]; int idx = 0, lo = 1, hi = k + 1;
while (lo <= hi) {
out[idx++] = lo++;
if (lo <= hi) out[idx++] = hi--;
}
for (int v = k + 2; v <= n; v++) out[idx++] = v;
return out;
}vector constructArray(int n, int k) {
vector out; int lo = 1, hi = k + 1;
while (lo <= hi) { out.push_back(lo++); if (lo <= hi) out.push_back(hi--); }
for (int v = k + 2; v <= n; v++) out.push_back(v);
return out;
} Explanation
We must build a permutation of 1..n so that the set of absolute differences between neighbors has exactly k distinct values. The neat insight is that we can manufacture exactly k different gaps with a simple zig-zag pattern, then pad the rest with trivial gaps of 1.
For the first part we take the range 1..k+1 and alternate from the two ends inward: 1, k+1, 2, k, 3, .... Each jump between these alternating picks produces a different difference: k, then k-1, then k-2, all the way down, giving exactly k distinct values.
After that zig-zag, the remaining numbers k+2, k+3, ..., n are simply appended in order. Consecutive numbers differ by 1, and 1 already appeared among the earlier gaps, so they add no new distinct differences.
The code does this with two pointers lo (starting at 1) and hi (starting at k+1), pushing them alternately until they meet, then looping v from k+2 to n.
Example: n=3, k=2. The zig-zag over 1..3 gives 1, 3, 2 with diffs 2 and 1 — exactly 2 distinct values. There's nothing left to append, so the answer is [1, 3, 2].