# 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:

```text
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

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | Any beautiful permutation of `[1, n]` |
| Valid array | A permutation with no forbidden arithmetic-average pattern |
| Constraint | `1 <= n <= 1000` |

Function shape:

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

## Examples

Example 1:

```python
n = 4
```

One valid answer is:

```python
[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:

```python
n = 5
```

One valid answer is:

```python
[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:

```text
i < k < j
```

and reject the permutation if:

```text
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:

```text
odd + even = odd
```

But:

```text
2 * nums[k]
```

is always even.

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

```text
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:

| Smaller beautiful value `x` | Transformed value |
|---|---|
| Left side | `2 * x - 1` |
| Right side | `2 * x` |

The left side creates odd numbers.

The right side creates even numbers.

## Algorithm

For `n == 1`, return:

```python
[1]
```

Otherwise:

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

```python
(n + 1) // 2
```

2. Convert it to odd numbers:

```python
2 * x - 1
```

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

```python
n // 2
```

4. Convert it to even numbers:

```python
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:

```python
n = 5
```

We split into:

```text
odd side size  = 3
even side size = 2
```

Build `beautifulArray(3)`.

That becomes:

```python
[1, 3, 2]
```

Convert to odd values:

```text
1 -> 1
3 -> 5
2 -> 3
```

So the odd side is:

```python
[1, 5, 3]
```

Build `beautifulArray(2)`.

That becomes:

```python
[1, 2]
```

Convert to even values:

```text
1 -> 2
2 -> 4
```

So the even side is:

```python
[2, 4]
```

Combine:

```python
[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:

```text
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:

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Each recursive level processes all values once |
| Space | `O(n log n)` | Recursive lists are created at each level |

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

## Implementation

```python
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:

```python
if n == 1:
    return [1]
```

A one-element array is always beautiful.

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

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

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

```python
right = self.beautifulArray(n // 2)
```

Convert the left side into odd numbers:

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

Convert the right side into even numbers:

```python
evens = [2 * x for x in right]
```

Then concatenate:

```python
return odds + evens
```

The odd side comes first, then the even side.

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `n = 1` | Base case |
| `n = 4` | Official example size |
| `n = 5` | Odd length |
| `1..20` | Validates many generated arrays |
| Permutation check | Confirms all numbers appear once |