# Solution by awice

• #### 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);
} 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 length `n`.

#### Approach #2: Construction [Accepted]

Intuition

When `k = n-1`, a valid construction is `[1, n, 2, n-1, 3, n-2, ....]`. One way to see this is, we need to have a difference of `n-1`, which means we need `1` and `n` adjacent; then, we need a difference of `n-2`, etc.

Also, when `k = 1`, a valid construction is `[1, 2, 3, ..., n]`. So we have a construction when `n-k` 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, ..., n-k-1]` first so that `n` is effectively `k+1`, and then finish the construction with the first "`k = n-1`" 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, ..., n-k-1]` first. The remaining `k+1` elements to be written are `[n-k, n-k+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 `n-k + 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(n-k + 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 < n-k; v++) {
ans[c++] = v;
}
for (int i = 0; i <= k; i++) {
ans[c++] = (i%2 == 0) ? (n-k + 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`.

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