Solution


Approach #1: Brute Force [Time Limit Exceeded]

Intuition

For each permutation of , 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 in the interval .

Complexity Analysis

  • Time Complexity: to generate every permutation in the outer loop, then work to check differences. In total taking time.

  • Space Complexity: . We use to store whether we've seen the differences, and each generated permutation has a length equal to .


Approach #2: Construction [Accepted]

Intuition

When , a valid construction is . One way to see this is, we need to have a difference of , which means we need and adjacent; then, we need a difference of , etc.

Also, when , a valid construction is . So we have a construction when is tiny, and when it is large. This leads to the idea that we can stitch together these two constructions: we can put first so that is effectively , and then finish the construction with the first method.

For example, when and , we will construct the array as . This consists of two parts: a construction of and a construction of where every element had added to it (i.e. ).

Algorithm

As before, write first. The remaining elements to be written are , and we'll write them in alternating head and tail order.

When we are writing the element from the remaining , every even is going to be chosen from the head, and will have value . Every odd is going to be chosen from the tail, and will have value .

Complexity Analysis

  • Time Complexity: . We are making a list of size .

  • Space Complexity: . Our answer has a length equal to .


Analysis written by: @awice