Problem Description

You need to create a "beautiful" array that satisfies two specific conditions:

1. The array must be a permutation of integers from 1 to n (meaning it contains each number from 1 to n exactly once)

2. For any three positions i, k, j where i < k < j, the element at position k cannot be the arithmetic mean of the elements at positions i and j. In other words, nums[k] should never equal (nums[i] + nums[j]) / 2, or equivalently, 2 * nums[k] should never equal nums[i] + nums[j].

The second condition essentially means that no element in the array should be positioned between two other elements such that it forms an arithmetic progression with them.

For example, if n = 4, an array like [2, 1, 4, 3] would be beautiful because:

• It contains all numbers from 1 to 4
• No element is the arithmetic mean of any two elements that surround it in the array

The solution uses a divide-and-conquer approach with a key insight: if you separate odd and even numbers, you can never have an arithmetic mean relationship between them. The algorithm recursively builds beautiful arrays for smaller sizes and combines them by:

• Taking the left half and converting all elements to odd numbers using the formula 2x - 1
• Taking the right half and converting all elements to even numbers using the formula 2x
• Concatenating these two halves

This ensures that any triplet (nums[i], nums[k], nums[j]) where i < k < j either has all odd numbers, all even numbers, or a mix - and in the mixed case, the arithmetic mean property cannot hold since the sum of an odd and even number is odd, which cannot equal twice an integer from the other parity.

Intuition

The key insight comes from thinking about what makes the arithmetic mean condition fail. If we have three numbers where 2 * nums[k] = nums[i] + nums[j], this means nums[k] is exactly the average of nums[i] and nums[j].

Let's think about when this arithmetic mean relationship can occur. For any three numbers to have this property, the middle value must be exactly halfway between the other two. This got me thinking - what if we could ensure that for any triplet in our array, the middle element can never be the average?

Here's the crucial observation: if one number is odd and another is even, their sum is always odd. An odd number divided by 2 cannot give us an integer, so there's no integer that can be the arithmetic mean of an odd and even number.

This leads to a powerful strategy: what if we separate odd and even numbers? If we place all odd numbers together and all even numbers together, then any triplet that crosses the boundary between odd and even sections cannot satisfy the arithmetic mean property.

But wait - we still need to ensure that within the odd section and within the even section, no arithmetic progressions exist. This is where recursion becomes brilliant.

If we have a beautiful array of size m, we can transform it into:

• An "all odd" beautiful array by applying 2x - 1 to each element
• An "all even" beautiful array by applying 2x to each element

Why does this transformation preserve the beautiful property? If originally 2 * b ≠ a + c for any valid positions, then after transforming to odds: 2 * (2b - 1) = 4b - 2 and (2a - 1) + (2c - 1) = 2a + 2c - 2 = 2(a + c) - 2. Since 2b ≠ a + c, we have 4b - 2 ≠ 2(a + c) - 2, so the property is preserved.

The same logic applies for the even transformation. By recursively building smaller beautiful arrays and combining them through odd/even separation, we construct our final beautiful array.

Learn more about Math and Divide and Conquer patterns.

Solution Approach

The implementation uses a divide-and-conquer strategy with recursion to build the beautiful array. Here's how the algorithm works step by step:

Base Case: When n = 1, we simply return [1] since a single-element array is trivially beautiful.

Recursive Division: For n > 1, we divide the problem into two subproblems:

• Left subproblem: Build a beautiful array of size (n + 1) >> 1 (which is (n + 1) // 2)
• Right subproblem: Build a beautiful array of size n >> 1 (which is n // 2)

This division ensures that left_size + right_size = n. When n is odd, the left part gets one more element than the right part.

Transformation to Odd and Even:

• Transform the left beautiful array to contain only odd numbers: x * 2 - 1 for each element x
• Transform the right beautiful array to contain only even numbers: x * 2 for each element x

For example, if the left subarray is [1, 2], it becomes [1, 3] after the odd transformation. If the right subarray is [1], it becomes [2] after the even transformation.

Concatenation: Combine the transformed arrays by placing all odd numbers first, followed by all even numbers: return left + right

Why This Works:

1. The transformation maintains the beautiful property within each half (as proven in the intuition)
2. The ranges don't overlap: odds go from 1 to 2*((n+1)//2) - 1, evens go from 2 to 2*(n//2)
3. Together they form a permutation of [1, n]
4. No arithmetic progression can span across the odd-even boundary

Example Trace for n = 4:

• beautifulArray(4) calls beautifulArray(2) for left and beautifulArray(2) for right
• beautifulArray(2) calls beautifulArray(1) for left and beautifulArray(1) for right
  • Returns [1] and [1], transforms to [1] and [2], combines to [1, 2]
• Back to beautifulArray(4): gets [1, 2] for both left and right
• Transforms left [1, 2] to odds: [1, 3]
• Transforms right [1, 2] to evens: [2, 4]
• Final result: [1, 3, 2, 4]

The time complexity is O(n log n) since we make recursive calls that process all n elements at each level of recursion, and there are O(log n) levels.

Example Walkthrough

Let's walk through building a beautiful array for n = 5 to see how the divide-and-conquer approach works.

Step 1: Initial Call beautifulArray(5) needs to create a permutation of [1, 2, 3, 4, 5].

• Left size: (5 + 1) >> 1 = 3
• Right size: 5 >> 1 = 2

Step 2: Build Left Subarray (size 3) beautifulArray(3) recursively calls:

• Left size: (3 + 1) >> 1 = 2
• Right size: 3 >> 1 = 1

For the left part, beautifulArray(2):

• Calls beautifulArray(1) twice, getting [1] and [1]
• Transforms: left [1] → odd: [1], right [1] → even: [2]
• Result: [1, 2]

For the right part, beautifulArray(1) returns [1]

Now combine for beautifulArray(3):

• Left [1, 2] → odds: [1, 3] (apply 2x - 1)
• Right [1] → evens: [2] (apply 2x)
• Result: [1, 3, 2]

Step 3: Build Right Subarray (size 2) beautifulArray(2) (as computed before) returns [1, 2]

Step 4: Final Combination Back in beautifulArray(5):

• Left [1, 3, 2] → odds: [1, 5, 3] (apply 2x - 1)
• Right [1, 2] → evens: [2, 4] (apply 2x)
• Final result: [1, 5, 3, 2, 4]

Verification: Let's verify this is beautiful by checking some triplets:

• (1, 5, 3): 2×5 = 10, but 1+3 = 4 ✓
• (1, 3, 2): 2×3 = 6, but 1+2 = 3 ✓
• (5, 3, 2): 2×3 = 6, but 5+2 = 7 ✓
• (3, 2, 4): 2×2 = 4, but 3+4 = 7 ✓

Notice how the odd numbers [1, 5, 3] are grouped together on the left, and even numbers [2, 4] on the right. Any triplet spanning this boundary (like 5, 3, 2) cannot form an arithmetic progression because we're mixing odd and even numbers.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses divide-and-conquer approach where:

• Each recursive call processes half the elements: T(n) = 2*T(n/2) + O(n)
• The O(n) work comes from creating the new arrays with list comprehensions
• Using the Master Theorem: a = 2, b = 2, f(n) = O(n)
• Since log_b(a) = log_2(2) = 1 and f(n) = O(n^1), we have Case 2
• Therefore, T(n) = O(n log n)

However, due to memoization implicit in the beautiful array construction (each subproblem size appears only once in the recursion tree), each number from 1 to n is processed exactly once across all recursive calls, giving us O(n) time complexity.

Space Complexity: O(n)

The space complexity consists of:

• Recursion stack depth: O(log n) (the tree has logarithmic height)
• Space for storing intermediate arrays: At each level of recursion, we create arrays whose total size sums to O(n)
• The dominant factor is the space needed to store the output array of size n
• Total space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Size Division for Odd n

A common mistake is incorrectly dividing the array size when n is odd. Developers might write:

left_half = self.beautifulArray(n // 2)
right_half = self.beautifulArray(n // 2)

This loses one element when n is odd (e.g., for n=5, we'd only process 4 elements total).

Solution: Use ceiling division for the left half and floor division for the right half:

left_half = self.beautifulArray((n + 1) // 2)  # or (n + 1) >> 1
right_half = self.beautifulArray(n // 2)        # or n >> 1

2. Incorrect Transformation Formulas

Some might accidentally swap or miswrite the transformation formulas:

# Wrong: swapped formulas
odd_numbers = [x * 2 for x in left_half]      # This creates evens!
even_numbers = [x * 2 - 1 for x in right_half] # This creates odds!

Solution: Remember that odd transformation is 2x - 1 and even transformation is 2x:

odd_numbers = [x * 2 - 1 for x in left_half]   # Correct: creates odds
even_numbers = [x * 2 for x in right_half]     # Correct: creates evens

3. Forgetting the Base Case

Omitting or incorrectly implementing the base case leads to infinite recursion:

def beautifulArray(self, n: int) -> List[int]:
    # Missing base case - infinite recursion!
    left_half = self.beautifulArray((n + 1) // 2)
    right_half = self.beautifulArray(n // 2)
    # ...

Solution: Always include the base case for n = 1:

if n == 1:
    return [1]

4. Wrong Concatenation Order

Concatenating in the wrong order doesn't affect the beautiful property but might fail test cases that expect a specific pattern:

# While still beautiful, might not match expected output
return even_numbers + odd_numbers  # Wrong order

Solution: Maintain consistent ordering (typically odds first, then evens):

return odd_numbers + even_numbers

5. Attempting to Verify the Result

Trying to verify if the array is beautiful using a brute force check can be inefficient and unnecessary:

# Unnecessary O(n³) verification
result = odd_numbers + even_numbers
for i in range(len(result)):
    for j in range(i + 2, len(result)):
        for k in range(i + 1, j):
            if 2 * result[k] == result[i] + result[j]:
                return []  # Wrong approach!
return result

Solution: Trust the algorithm's correctness. The divide-and-conquer approach with odd-even separation mathematically guarantees the beautiful property.