# c++ O(n) solution with a simple proof

• I have no idea when I first saw this problem. That's why we need to exam the small cases.
The test example is a good inspiration. When consider n = 3, k = 2 with array [1, 3, 2], you may notice that it gives you 1, 2 these two distinct integers. If we want to have k distinct integers from 1, ..., k, what we can do?

A nature way is to mimic the example. We put 1 in the first, then k + 1 in order to get k. The we put 2 to get k - 1, then k to get k - 2 and so on. For example, [1, k+1, 2, k, 3, k-1, ..., ]. The process will stop when we hit the integer k/2 + 1 for k = even and (k + 3) / 2 for k = odd. By doing so, we get the integers from 1 to k. Now, we need to take care of the next integer. Since we used up from 1 to k+1, then k+2 comes to the next. We can easily check that k+2 - (k/2 + 1) or (k+2) - (k+3)/2 are smaller or equal to k. Then we are done if we put k+2, k+3, ... n to the remaining of the array.

``````class Solution {
public:
vector<int> constructArray(int n, int k) {
//Put 1...k+1 in the first half of the array
vector<int> array(n);
int left = 1;
int right = k + 1;
int idx = 0;
while (left <= right) {
if (left < right) {
array[idx++] = left;
array[idx++] = right;
} else {
array[idx++] = left;
}
left++;
right--;
}
for (int i = idx; i < n; i++) {
array[i] = k + i - idx + 2;
}
return array;
}
};
``````

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