Beautiful Arrangement II

The problem is about constructing an array of n different positive integers such that the array of absolute differences between adjacent elements contains exactly k distinct integers. We can achieve this by following these steps:

  1. Initialize the Array: Start by placing numbers 1 through n-k-1 in order in the array.
  2. Add k Distinct Differences: Now, we need to create k distinct differences between the adjacent elements. For this, we can alternate between adding and subtracting from n-k to create the required distinct differences.
  3. Build the Array: Keep adding elements to the array, alternating between adding and subtracting the next number until we have added k numbers.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        # Initialize the result array with numbers from 1 to n-k-1
        result = [i for i in range(1, n-k)]

        # Add the next k numbers by alternating between adding and subtracting
        for i in range(k+1):
            if i % 2 == 0:
                result.append(n-k + i//2)
            else:
                result.append(n - i//2)

        return result

Explanation:

  • We first initialize the result array with numbers from 1 to n-k-1.
  • Then, we add the next k+1 numbers to create k distinct differences between adjacent elements.
  • We add and subtract numbers in an alternating manner to ensure that the differences are distinct.

For example, given n = 3, k = 2, the output will be [1, 3, 2]. The array has three different positive integers, and the absolute differences are [2, 1], which has exactly 2 distinct integers.