# C++, concise code, O(n)

• The requirement of k distinct distance can be achieved from 1, 2, ..., k+1 (<= n), by the following strategy:

``````1, k+1, 2, k, 3, k-1 ...;
The distance of this sequence is k, k-1, k-2, ..., 2, 1
``````

Then append the remaining numbers to the list.

``````class Solution {
public:
vector<int> constructArray(int n, int k) {
int l = 1, r = k+1;
vector<int> ans;
while (l <= r) {
ans.push_back(l++);
if (l <= r) ans.push_back(r--);
}
for (int i = k+2; i <= n; i++)
ans.push_back(i);
return ans;
}
};
``````

• Java version based on the same idea:

``````class Solution {
public int[] constructArray(int n, int k) {
int[] res = new int[n];
int l = 1, r = k + 1, i = 0;
while (l <= r) {
res[i++] = l++;
if (l <= r)
res[i++] = r--;
}
for (int j = 0; j + i < n; j++) {
res[j + i] = k + 2 + j;
}
return res;
}
}
``````

Also, I think a certain point need to be clarified. In the case of `(n,k) = (5,3)`, we first arrange `1..4` and then append `5`, we have `1 4 2 3` + `5`. It is for sure that there will be `3` diffs in `1 4 2 3`, but it remains to be proved that `3 5` won't introduce an additional distinct diff (everything after 5, if any, need not to be worried, since they all form diff of `1`, and is surely covered by the `k` diffs of `1..k+1`).
The proof of this is actually pretty trivial, since `5`, which is `k+2` can only introduce a new diff with the trailing number of whatever the result that is formed from `1..k+1`, this trailing diff can only be within the range of `1..k+1`. Don't panic for now, `k+1` is actually untenable: to produce diff of `k+1`, we have to make sure that the subarray formed from `1..k+1` ends with `1`, and this will never be the case: even when `k` is smallest as 1, the trailing number will be 2, and the maximum of the newly introduced trailing diff can only be `k`. Thus the trailing diff is in the range of `1..k`, and there is nothing new that has not already been covered by the subarray formed from `1..k+1`. In total, the entire array still contributes only `k` distinct diffs.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.