{x}
blog image

Beautiful Arrangement II

Given two integers n and k, construct a list answer that contains n different positive integers ranging from 1 to n and obeys the following requirement:

  • Suppose this list is answer = [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.

Return the list answer. If there multiple valid answers, return any of them.

 

Example 1:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

Example 2:

Input: n = 3, k = 2
Output: [1,3,2]
Explanation: The [1,3,2] has three different positive integers ranging from 1 to 3, and the [2,1] has exactly 2 distinct integers: 1 and 2.

 

Constraints:

  • 1 <= k < n <= 104

Solution Explanation for Beautiful Arrangement II

The problem asks to construct an array of length n containing distinct integers from 1 to n, such that the absolute differences between consecutive elements have exactly k distinct values.

Approach

The solution leverages a pattern to construct the array. It iteratively adds elements, alternating between the smallest and largest remaining unused numbers. This creates a sequence of differences that increases and then decreases, ensuring the desired number of distinct differences.

Algorithm

  1. Initialization: Initialize two pointers, l and r, to 1 and n respectively. These represent the smallest and largest remaining numbers. Initialize an empty array ans to store the result.

  2. Iterative Construction (k iterations): The loop runs k times. In each iteration:

    • If the iteration index i is even, append l to ans and increment l.
    • If i is odd, append r to ans and decrement r. This alternating pattern creates the desired differences.

  3. Filling the Remaining Elements: After the first k elements, the remaining n-k elements are added. If k is even, the remaining elements are added in decreasing order from r; otherwise, they're added in increasing order from l. This ensures that the differences do not introduce additional distinct values.

  4. Return: The array ans is returned.

Time and Space Complexity

  • Time Complexity: O(n), as the algorithm iterates through the numbers from 1 to n once.
  • Space Complexity: O(n), to store the resulting array ans.

Code Explanation (Python)

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        l, r = 1, n
        ans = []
        for i in range(k):
            if i % 2 == 0:
                ans.append(l)
                l += 1
            else:
                ans.append(r)
                r -= 1
        for i in range(k, n):
            if k % 2 == 0:
                ans.append(r)
                r -= 1
            else:
                ans.append(l)
                l += 1
        return ans

The Python code directly implements the algorithm described above. The if i % 2 == 0 conditions handle the alternating addition of l and r during the first k iterations, while the subsequent loop fills the remaining array elements based on the parity of k.

The Java, C++, Go and TypeScript implementations follow the same logic and have the same time and space complexity. They only differ in syntax and data structures used.