Sponsored
Sponsored
The idea here is to create a pattern with the integers that alternates between choosing numbers from the start and the end of a range. This provides the necessary number of distinct absolute differences between consecutive elements.
We build the answer list by initially alternating between numbers from opposite ends of a list of size n. Then, we fill in the remaining elements in a simple sequence.
Time Complexity: O(n), as we build the array in a single pass.
Space Complexity: O(n), for storing the answer.
1def constructArray(n, k):
2 answer = []
3 low, high = 1, n
4 for i in range(k + 1):
5 if i % 2 == 0:
6 answer.append(low)
7 low += 1
8 else:
9 answer.append(high)
10 high -= 1
11 if k % 2 == 0:
12 answer.extend(range(high, low - 1, -1))
13 else:
14 answer.extend(range(low, high + 1))
15 return answerThe function constructArray creates a list using a two-pointer approach. It alternates between adding the current low and high indices, and adjusts them after each addition.
After reaching k + 1 positions, it fills up the remaining part of the array.
This approach constructs the answer using a specific pattern that alternates addition and subtraction. It builds the sequence by starting linearly and then intelligently adds or subtracts to reach necessary differences.
Time Complexity: O(n), iterating through the elements.
Space Complexity: O(n), owing to the storage of results.
1function constructArray(n, k) {
2 This JavaScript solution constructs the array first by filling straightforward values, then follows pattern-based alternate increments and decrements to fill in necessary distinct differences.