Approach #1: Brute Force [Time Limit Exceeded]
Intuition
For each permutation of [1, 2, ..., n]
, let's look at the set of differences of the adjacent elements.
Algorithm
For each permutation, we find the number of unique differences of adjacent elements. If it is the desired number, we'll return that permutation.
To enumerate each permutation without using library functions, we use a recursive algorithm, where permute
is responsible for permuting the indexes of nums
in the interval [start, nums.length)
.
Python
class Solution(object):
def constructArray(self, n, k):
seen = [False] * n
def num_uniq_diffs(arr):
ans = 0
for i in range(n):
seen[i] = False
for i in range(len(arr)  1):
delta = abs(arr[i]  arr[i+1])
if not seen[delta]:
ans += 1
seen[delta] = True
return ans
for cand in itertools.permutations(range(1, n+1)):
if num_uniq_diffs(cand) == k:
return cand
Java
class Solution {
private ArrayList<ArrayList<Integer>> permutations(int[] nums) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
permute(ans, nums, 0);
return ans;
}
private void permute(ArrayList<ArrayList<Integer>> ans, int[] nums, int start) {
if (start >= nums.length) {
ArrayList<Integer> cur = new ArrayList<Integer>();
for (int x : nums) cur.add(x);
ans.add(cur);
} else {
for (int i = start; i < nums.length; i++) {
swap(nums, start, i);
permute(ans, nums, start+1);
swap(nums, start, i);
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private int numUniqueDiffs(ArrayList<Integer> arr) {
boolean[] seen = new boolean[arr.size()];
int ans = 0;
for (int i = 0; i < arr.size()  1; i++) {
int delta = Math.abs(arr.get(i)  arr.get(i+1));
if (!seen[delta]) {
ans++;
seen[delta] = true;
}
}
return ans;
}
public int[] constructArray(int n, int k) {
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = i+1;
}
for (ArrayList<Integer> cand : permutations(nums)) {
if (numUniqueDiffs(cand) == k) {
int[] ans = new int[n];
int i = 0;
for (int x : cand) ans[i++] = x;
return ans;
}
}
return null;
}
}
Complexity Analysis

Time Complexity: $$O(n!)$$ to generate every permutation in the outer loop, then $$O(n)$$ work to check differences. In total, $$O(n * n!)$$.

Space Complexity: $$O(n)$$. We use
seen
to store whether we've seen the differences, and each generated permutation is lengthn
.
Approach #2: Construction [Accepted]
Intuition
When k = n1
, a valid construction is [1, n, 2, n1, 3, n2, ....]
. One way to see this is, we need to have a difference of n1
, which means we need 1
and n
adjacent; then, we need a difference of n2
, etc.
Also, when k = 1
, a valid construction is [1, 2, 3, ..., n]
. So we have a construction when nk
is tiny, and when it is large. This leads to the idea that we can stitch together these two constructions: we can put [1, 2, ..., nk1]
first so that n
is effectively k+1
, and then finish the construction with the first "k = n1
" method.
For example, when n = 6
and k = 3
, we will construct the array as [1, 2, 3, 6, 4, 5]
. This consists of two parts: a construction of [1, 2]
and a construction of [1, 4, 2, 3]
where every element had 2
added to it (ie. [3, 6, 4, 5]
).
Algorithm
As before, write [1, 2, ..., nk1]
first. The remaining k+1
elements to be written are [nk, nk+1, ..., n]
, and we'll write them in alternating head and tail order.
When we are writing the i
th element from the remaining k+1
, every even i
is going to be chosen from the head, and will have value nk + i//2
. Every odd i
is going to be chosen from the tail, and will have value n  i//2
.
Python
class Solution(object):
def constructArray(self, n, k):
ans = list(range(1, n  k))
for i in range(k+1):
if i % 2 == 0:
ans.append(nk + i//2)
else:
ans.append(n  i//2)
return ans
Java
class Solution {
public int[] constructArray(int n, int k) {
int[] ans = new int[n];
int c = 0;
for (int v = 1; v < nk; v++) {
ans[c++] = v;
}
for (int i = 0; i <= k; i++) {
ans[c++] = (i%2 == 0) ? (nk + i/2) : (n  i/2);
}
return ans;
}
}
Complexity Analysis

Time Complexity: $$O(n)$$. We are making a list of size
n
. 
Space Complexity: $$O(n)$$. Our answer is length
n
.