LeetCode 932: Beautiful Array

Problem Restatement

We are given an integer n.

We need to return any array nums of length n such that:

1. nums is a permutation of integers from 1 to n.
2. For every i < j, there is no index k with i < k < j such that:

2 * nums[k] == nums[i] + nums[j]

In other words, no middle-position value may be the arithmetic average of a value before it and a value after it.

The problem guarantees that at least one valid answer exists. The constraints are 1 <= n <= 1000.

Input and Output

Function shape:

class Solution:
    def beautifulArray(self, n: int) -> list[int]:
        ...

Examples

Example 1:

n = 4

One valid answer is:

[2, 1, 4, 3]

Check the condition.

There is no triple of indices i < k < j where the middle value is exactly the average of the outer values.

Example 2:

n = 5

One valid answer is:

[3, 1, 2, 5, 4]

The output does not need to be unique. Any valid beautiful array is accepted.

First Thought: Search All Permutations

A direct approach is to generate every permutation of [1, n] and test whether it is beautiful.

For each permutation, we would check every triple of indices:

i < k < j

and reject the permutation if:

2 * nums[k] == nums[i] + nums[j]

This is not practical.

There are n! permutations, and each one needs many checks. We need to construct a valid permutation directly.

Key Insight

The condition fails when three values form an arithmetic progression in index order.

The useful parity fact is:

odd + even = odd

But:

2 * nums[k]

is always even.

So if nums[i] and nums[j] have different parity, then:

nums[i] + nums[j]

is odd, and it can never equal 2 * nums[k].

This suggests splitting the answer into odd numbers and even numbers.

If all odd numbers are placed before all even numbers, then any triple crossing the boundary is automatically safe because the two outer values have different parity.

Now we only need each side itself to be beautiful.

That gives a recursive construction:

The left side creates odd numbers.

The right side creates even numbers.

Algorithm

For n == 1, return:

[1]

Otherwise:

1. Build a beautiful array for the odd side size:

(n + 1) // 2

2. Convert it to odd numbers:

2 * x - 1

3. Build a beautiful array for the even side size:

n // 2

4. Convert it to even numbers:

2 * x

5. Return odd side followed by even side.

This is the same divide-and-conquer construction commonly used for this problem.

Walkthrough

Use:

n = 5

We split into:

odd side size  = 3
even side size = 2

Build beautifulArray(3).

That becomes:

[1, 3, 2]

Convert to odd values:

1 -> 1
3 -> 5
2 -> 3

So the odd side is:

[1, 5, 3]

Build beautifulArray(2).

That becomes:

[1, 2]

Convert to even values:

1 -> 2
2 -> 4

So the even side is:

[2, 4]

Combine:

[1, 5, 3, 2, 4]

This is a valid beautiful array for n = 5.

The official example shows [3,1,2,5,4], but many valid answers are allowed.

Correctness

First, the returned array is a permutation of [1, n].

The recursive left side has values from 1 to (n + 1) // 2. After applying 2 * x - 1, it becomes exactly all odd numbers from 1 to n.

The recursive right side has values from 1 to n // 2. After applying 2 * x, it becomes exactly all even numbers from 1 to n.

Together, the two sides contain every number from 1 to n exactly once.

Now we prove the beautiful condition.

A useful property is that if an array is beautiful, then applying a linear transformation:

x -> a * x + b

with positive integer a preserves the beautiful condition. If a forbidden equality existed after transformation, then the same equality would imply a forbidden equality before transformation.

So the transformed odd side remains beautiful, and the transformed even side remains beautiful.

Now consider any triple i < k < j.

If all three indices lie inside the odd side, the condition is false because the odd side is beautiful.

If all three indices lie inside the even side, the condition is false because the even side is beautiful.

The remaining case crosses the boundary between odd and even sides. Since the array places all odd values before all even values, the outer values nums[i] and nums[j] have different parity. Their sum is odd, while 2 * nums[k] is even. Therefore:

2 * nums[k] != nums[i] + nums[j]

So no forbidden triple exists.

By induction, the algorithm returns a beautiful array for every valid n.

Complexity

With memoization, the construction can reuse smaller arrays, but n <= 1000, so the direct recursive version is sufficient.

Implementation

class Solution:
    def beautifulArray(self, n: int) -> list[int]:
        if n == 1:
            return [1]

        left = self.beautifulArray((n + 1) // 2)
        right = self.beautifulArray(n // 2)

        odds = [2 * x - 1 for x in left]
        evens = [2 * x for x in right]

        return odds + evens

Code Explanation

The base case is a single value:

if n == 1:
    return [1]

A one-element array is always beautiful.

The left recursive call builds the shape for the odd values:

left = self.beautifulArray((n + 1) // 2)

The right recursive call builds the shape for the even values:

right = self.beautifulArray(n // 2)

Convert the left side into odd numbers:

odds = [2 * x - 1 for x in left]

Convert the right side into even numbers:

evens = [2 * x for x in right]

Then concatenate:

return odds + evens

The odd side comes first, then the even side.

Testing

def is_beautiful(arr):
    n = len(arr)

    if sorted(arr) != list(range(1, n + 1)):
        return False

    for i in range(n):
        for k in range(i + 1, n):
            for j in range(k + 1, n):
                if 2 * arr[k] == arr[i] + arr[j]:
                    return False

    return True

def run_tests():
    s = Solution()

    for n in range(1, 21):
        ans = s.beautifulArray(n)
        assert is_beautiful(ans), (n, ans)

    assert len(s.beautifulArray(1)) == 1
    assert sorted(s.beautifulArray(4)) == [1, 2, 3, 4]
    assert sorted(s.beautifulArray(5)) == [1, 2, 3, 4, 5]

    print("all tests passed")

run_tests()