# My java O(n) greedy solution

• The k distinct differences can be conveniently chosen to be 1, 2, 3 ... k. To make sure the biggest difference "k" exists, we may start from the smallest number 1, and then take 1 + k in the second position next to it. The second largest difference k - 1 can be obtained by setting the third number as k + 1 - (k - 1). We can similarly select the rest numbers following this small-big-small pattern: array[i] = array[i - 1] + / - (k - i + 1). For numbers that have not been used (from k + 2 to n), we just leave them in increasing order which won't produce new distinct differences.

``````class Solution {
public int[] constructArray(int n, int k) {
int[] array = new int[n];
array[0] = 1;
for (int i = 1; i <= k; i++) {
if ((i & 1) != 0)
array[i] = array[i - 1] + k - i + 1;
else
array[i] = array[i - 1] - k + i - 1;
}
for (int i = k + 1; i < n; i++)
array[i] = i + 1;
return array;
}
}
``````

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