#932

Medium

LeetCode Problem Workspace

Beautiful Array

Beautiful Array builds a valid permutation by recursively separating odd and even positions so no middle-average triple can appear.

array math divide and conquer

Problem Statement

You need to return a permutation of the integers from 1 to n such that for every pair of positions i < j, there is no index k with i < k < j where nums[k] is exactly the average of nums[i] and nums[j]. In other words, the array must avoid every three-position arithmetic pattern where the middle element sits between the other two indices and also equals their numeric midpoint.

This problem does not ask for the lexicographically smallest answer or a unique arrangement. Any permutation that satisfies the rule is acceptable. For example, when n = 4, one valid output is [2,1,4,3], because no element between two chosen positions becomes the exact average of the endpoints. The challenge is to generate such an array directly instead of testing many permutations.

Examples

Example 1

Input: n = 4

Output: [2,1,4,3]

Example details omitted.

Example 2

Input: n = 5

Output: [3,1,2,5,4]

Example details omitted.

Constraints

1 <= n <= 1000

Solution Approach

Use the odd-even closure property

The Beautiful Array pattern works because if a smaller array is already beautiful, then transforming each value x into 2x-1 keeps all values odd, and transforming x into 2x keeps all values even. Inside each transformed half, the no-average property is preserved, and across halves, an odd value and an even value cannot create an integer midpoint that lands in the wrong parity class. That parity split is the math reason this construction survives concatenation.

Build from a smaller beautiful array

Start with the base beautiful array [1]. Repeatedly generate a new list by first taking every current value x and adding 2x-1 if it is at most n, then taking every current value x and adding 2x if it is at most n. For n = 4, this grows as [1] -> [1,2] -> [1,3,2,4], and another valid ordering like [2,1,4,3] is also acceptable because the problem allows any beautiful permutation. The important part is the recursive odd-then-even expansion, not matching one exact output.

Why divide and conquer beats brute force

A brute force permutation search explodes immediately because most orderings violate the average condition somewhere in the middle. The divide and conquer construction avoids checking triples directly. It reduces the problem to solving the same structure on a smaller set, then lifts that solution through odd and even mappings. That is the exact trade-off in Beautiful Array: use math to guarantee validity instead of spending time detecting every forbidden triple after the fact.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	O(N \log N)

The standard construction runs in O(N \log N) time and uses O(N \log N) space across recursive or iterative list creation. Each expansion scans the current beautiful array and filters values that remain within 1 to n. The extra log factor comes from repeatedly rebuilding the array through smaller odd and even projections until it reaches size n.

What Interviewers Usually Probe

They want you to stop thinking in terms of local swaps and notice a global construction based on parity.
A strong answer explains why 2x-1 and 2x preserve beauty instead of only presenting code that seems to work.
If they ask for n = 4 or n = 5 by hand, they are checking whether you understand the recursive build, not memorized output.

Common Pitfalls or Variants

Common pitfalls

Trying to greedily place the next number often creates a later average collision that is hard to repair.
Assuming you must return the sample order is wrong; Beautiful Array accepts any valid permutation.
Forgetting to discard mapped values greater than n will break the permutation and produce duplicates or out-of-range numbers.

Follow-up variants

Return any beautiful ordering for only a subset of numbers, which keeps the same odd-even recursive idea but changes filtering.
Count how many forbidden average triples appear in a given permutation, which flips the problem from constructive math to verification.
Build the array iteratively with memoization versus top-down recursion, which tests whether you can preserve the same parity argument in a different implementation style.

FAQ

What is the core trick in Beautiful Array?

The trick is to build a smaller beautiful array first, then map it to odd values with 2x-1 and even values with 2x. Concatenating those two groups preserves the no-average rule because parity blocks cross-group midpoint conflicts.

Why does the odd-even construction work for the Array plus Math pattern?

Within the odd group and within the even group, the original relative structure is preserved from the smaller beautiful array. Across groups, one endpoint is odd and the other is even, so their average cannot land as a valid middle element in the required way for this construction.

Do I need to verify every i, k, j triple after building the array?

No. The point of the construction is that the proof gives you the guarantee. Once you correctly generate the array through the recursive odd and even mapping, explicit triple checking is unnecessary.

Why is brute force a bad fit for LeetCode 932?

Brute force treats Beautiful Array like a search problem over permutations, which grows far too fast and still needs expensive validation. The intended solution is constructive divide and conquer with a math invariant, so you never explore invalid orderings.

Can Beautiful Array have multiple correct answers?

Yes. The problem asks for any beautiful permutation from 1 to n. Sample outputs are only examples, so your answer does not need to match them exactly as long as it satisfies the no-middle-average condition.

terminal

Solution

Solution 1

#### Python3

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        if n == 1:
            return [1]
        left = self.beautifulArray((n + 1) >> 1)
        right = self.beautifulArray(n >> 1)
        left = [x * 2 - 1 for x in left]
        right = [x * 2 for x in right]
        return left + right

Continue Practicing

#973 k closest points to origin #1569 number of ways to reorder array to get same bst #927 three equal parts