LeetCode 932 - Beautiful Array

LeetCode Problem 932

Difficulty: 🟡 Medium
Topics: Array, Math, Divide and Conquer

Solution

Problem Understanding

The problem asks us to construct a permutation of the integers from 1 to n such that the array satisfies a special condition. Specifically, for every pair of indices i < j, there must not exist any index k between them where:

$2 \cdot nums[k] = nums[i] + nums[j]$

This condition means that no middle element can be the arithmetic mean of two surrounding elements. In other words, the array cannot contain any three values that form an arithmetic progression when arranged in index order.

The input consists of a single integer n, representing the size of the permutation we must generate. The output should be any valid beautiful array of length n. The problem guarantees that at least one solution always exists.

The constraints are relatively small, with n <= 1000, but the challenge is not raw performance from large input sizes. Instead, the challenge is discovering the mathematical structure that allows such arrays to be constructed efficiently.

A naive implementation could easily fail because checking every possible triple (i, k, j) would be extremely expensive. Another common issue is generating a valid permutation while simultaneously maintaining the beautiful property. Since every number from 1 to n must appear exactly once, careless construction methods may accidentally introduce arithmetic progressions.

Several edge cases are important:

• When n = 1, the only valid answer is [1].
• Small values like n = 2 or n = 3 are useful for verifying the construction logic.
• Larger values require ensuring that no hidden arithmetic progression appears after combining smaller subarrays.
• The solution must guarantee uniqueness of elements while preserving the beautiful property.

Approaches

Brute Force Approach

A brute force solution would attempt to generate permutations of the numbers from 1 to n and check whether each permutation satisfies the beautiful condition.

To validate a permutation, we would examine every pair (i, j) and check all indices k between them to determine whether:

$2 \cdot nums[k] = nums[i] + nums[j]$

If such a k exists, the permutation is invalid.

This method is correct because it directly tests the problem definition. However, it is computationally infeasible. There are n! permutations, and validating each permutation requires roughly O(n^3) time in the worst case. Even for moderate values of n, this becomes impossible.

Optimal Divide and Conquer Insight

The key insight is that the beautiful property is preserved under certain transformations.

Suppose we already have a beautiful array A. Then:

• Multiplying every element by 2 and subtracting 1 produces only odd numbers.
• Multiplying every element by 2 produces only even numbers.

Most importantly, both transformed arrays remain beautiful.

This works because arithmetic progression relationships are preserved under linear transformations. Additionally, odd and even numbers cannot combine to form the required equality condition.

The recursive structure becomes:

• Build a beautiful array for odd positions.
• Build a beautiful array for even positions.
• Concatenate them together.

For example:

• From [1]
• Generate odds: [1]
• Generate evens: [2]
• Combine into [1,2]

Then continue recursively:

• Odds from [1,2] become [1,3]
• Evens from [1,2] become [2,4]
• Combine into [1,3,2,4]

This construction guarantees correctness while avoiding brute force search entirely.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n³)	O(n)	Tries every permutation and validates each one
Optimal	O(n log n)	O(n)	Uses recursive divide and conquer construction

Algorithm Walkthrough

1. Start with a base beautiful array containing only [1].

A single element array is trivially beautiful because there are no triples to violate the condition. 2. Repeatedly expand the array using odd and even transformations.

For every number x in the current beautiful array:

• Generate an odd value using 2*x - 1
• Generate an even value using 2*x

3. Keep only values that are less than or equal to n.

The transformations may produce numbers larger than n, which are not allowed in the final permutation. 4. Construct the next beautiful array.

First append all valid odd values, then append all valid even values.

The ordering matters because:

• The odd portion remains beautiful internally.
• The even portion remains beautiful internally.
• Odd and even numbers cannot create forbidden arithmetic progressions together.

5. Continue expanding until the array contains n elements.

Since every iteration approximately doubles the number of valid elements, the process completes quickly.

Why it works

The core invariant is that every intermediate array remains beautiful.

If an array A is beautiful, then both transformed arrays:

$2A-1$

and

$2A$

are also beautiful because linear transformations preserve the absence of arithmetic progressions.

Furthermore, combining odd and even numbers cannot introduce violations because:

• The average of an odd and even number is not an integer.
• Therefore, no middle element can satisfy the beautiful condition across the two groups.

This guarantees that the final concatenated array is beautiful.

Python Solution

from typing import List

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        beautiful = [1]

        while len(beautiful) < n:
            next_array = []

            # Generate odd numbers
            for value in beautiful:
                odd = 2 * value - 1
                if odd <= n:
                    next_array.append(odd)

            # Generate even numbers
            for value in beautiful:
                even = 2 * value
                if even <= n:
                    next_array.append(even)

            beautiful = next_array

        return beautiful

The implementation starts with the base case [1], which is already beautiful.

The main loop repeatedly expands the current array. During each iteration, a new array is constructed in two phases.

The first phase generates odd numbers using 2 * value - 1. These values preserve the beautiful property because they are simply transformed versions of the previous beautiful array.

The second phase generates even numbers using 2 * value. Again, the beautiful property is preserved.

Values greater than n are skipped because the final permutation must only contain integers in the range [1, n].

Finally, the newly generated array replaces the previous one, and the process continues until exactly n valid values exist.

Go Solution

func beautifulArray(n int) []int {
    beautiful := []int{1}

    for len(beautiful) < n {
        nextArray := []int{}

        // Generate odd numbers
        for _, value := range beautiful {
            odd := 2*value - 1
            if odd <= n {
                nextArray = append(nextArray, odd)
            }
        }

        // Generate even numbers
        for _, value := range beautiful {
            even := 2 * value
            if even <= n {
                nextArray = append(nextArray, even)
            }
        }

        beautiful = nextArray
    }

    return beautiful
}

The Go implementation follows the same logic as the Python version.

Slices are used instead of dynamic lists. The append function handles dynamic resizing automatically.

Integer overflow is not a concern because n <= 1000, so all generated values remain very small relative to Go's integer limits.

Unlike Python, Go does not have built in list comprehensions, so explicit loops are used for constructing the odd and even portions.

Worked Examples

Example 1

Input:

n = 4

Initial state:

Step	Beautiful Array
Start	[1]

First expansion:

Current Value	Odd Transformation	Even Transformation
1	1	2

New array:

[1,2]

Second expansion:

Current Value	Odd Transformation	Even Transformation
1	1	2
2	3	4

New array:

[1,3,2,4]

This is a valid beautiful array.

Example 2

Input:

n = 5

Initial state:

[1]

First expansion:

[1,2]

Second expansion:

[1,3,2,4]

Third expansion:

Current Value	Odd Transformation	Even Transformation
1	1	2
3	5	6
2	3	4
4	7	8

Discard values greater than 5.

Final array:

[1,5,3,2,4]

This satisfies all beautiful array conditions.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each expansion processes the current array, and the array size roughly doubles each iteration
Space	O(n)	The algorithm stores the constructed beautiful array

The number of iterations is logarithmic because the array approximately doubles in size during each expansion. Across all iterations, the total number of processed elements is proportional to n log n.

The space complexity is linear because the algorithm only stores the current beautiful array and the next generated array.

Test Cases

from typing import List

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        beautiful = [1]

        while len(beautiful) < n:
            next_array = []

            for value in beautiful:
                odd = 2 * value - 1
                if odd <= n:
                    next_array.append(odd)

            for value in beautiful:
                even = 2 * value
                if even <= n:
                    next_array.append(even)

            beautiful = next_array

        return beautiful

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

    # Must be a permutation of 1..n
    assert sorted(arr) == list(range(1, n + 1))

    # Check beautiful condition
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(i + 1, j):
                assert 2 * arr[k] != arr[i] + arr[j]

    return True

solution = Solution()

# Boundary case: smallest input
assert is_beautiful(solution.beautifulArray(1))

# Small input
assert is_beautiful(solution.beautifulArray(2))

# Small odd size
assert is_beautiful(solution.beautifulArray(3))

# Example case
assert is_beautiful(solution.beautifulArray(4))

# Example case with odd n
assert is_beautiful(solution.beautifulArray(5))

# Medium-sized input
assert is_beautiful(solution.beautifulArray(10))

# Larger input
assert is_beautiful(solution.beautifulArray(50))

# Stress test near upper constraint
assert is_beautiful(solution.beautifulArray(1000))

Test	Why
n = 1	Validates smallest possible input
n = 2	Ensures simple even-sized arrays work
n = 3	Tests small odd-sized construction
n = 4	Verifies provided example scenario
n = 5	Verifies odd-length recursive expansion
n = 10	Confirms correctness for moderate input
n = 50	Tests larger recursive growth
n = 1000	Stress test at maximum constraint

Edge Cases

One important edge case is n = 1. A naive recursive solution might accidentally assume there are always multiple elements to divide or transform. In this implementation, the algorithm starts directly from [1], which already satisfies the beautiful condition, so the result is returned immediately.

Another critical edge case occurs when transformed values exceed n. During recursive expansion, values such as 2*x or 2*x-1 can become larger than the allowed range. If these values were included, the result would no longer be a valid permutation of 1 through n. The implementation explicitly filters values using if odd <= n and if even <= n.

A third edge case involves maintaining uniqueness while preserving the beautiful property. Some naive constructions accidentally duplicate values or skip numbers entirely. This implementation avoids that issue because the odd transformation always generates distinct odd numbers and the even transformation always generates distinct even numbers. Since odd and even sets are disjoint, duplicates cannot occur.

Another subtle edge case is ensuring that combining two valid beautiful arrays does not accidentally introduce arithmetic progressions across the boundary. The odd-even partition guarantees this cannot happen because the average of an odd and even number is fractional, making the forbidden equality impossible.