Code Implementation

class Solution:
    def beautifulArray(self, n: int) -> list[int]:
        res = [1]
        while len(res) < n:
            odds = [x * 2 - 1 for x in res if x * 2 - 1 <= n]
            evens = [x * 2 for x in res if x * 2 <= n]
            res = odds + evens
        return res
      

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> res{1};
        while (res.size() < n) {
            vector<int> odds, evens;
            for (int x : res) {
                if (x * 2 - 1 <= n) odds.push_back(x * 2 - 1);
            }
            for (int x : res) {
                if (x * 2 <= n) evens.push_back(x * 2);
            }
            res.clear();
            res.insert(res.end(), odds.begin(), odds.end());
            res.insert(res.end(), evens.begin(), evens.end());
        }
        return res;
    }
};
      

class Solution {
    public int[] beautifulArray(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(1);
        while (res.size() < n) {
            List<Integer> odds = new ArrayList<>();
            List<Integer> evens = new ArrayList<>();
            for (int x : res) {
                if (x * 2 - 1 <= n) odds.add(x * 2 - 1);
            }
            for (int x : res) {
                if (x * 2 <= n) evens.add(x * 2);
            }
            res.clear();
            res.addAll(odds);
            res.addAll(evens);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) ans[i] = res.get(i);
        return ans;
    }
}
      

var beautifulArray = function(n) {
    let res = [1];
    while (res.length < n) {
        let odds = res.map(x => x * 2 - 1).filter(x => x <= n);
        let evens = res.map(x => x * 2).filter(x => x <= n);
        res = odds.concat(evens);
    }
    return res;
};
      

Problem Description

Given a positive integer n, you are to construct a beautiful array of length n. An array is called beautiful if, for every pair of indices i < j, there does NOT exist a k such that i < k < j and nums[k] * 2 = nums[i] + nums[j]. In other words, no element in the array is the average of any two other elements between which it lies.

You must return any beautiful array of length n (there may be multiple valid answers), using each number from 1 to n exactly once.

• Input: n (integer, 1 ≤ n ≤ 1000)
• Output: Array of length n with all integers from 1 to n (inclusive), arranged to form a beautiful array
• Constraints: Each integer must appear exactly once; only one valid solution is required.

Thought Process

At first glance, the problem seems to ask for a permutation of numbers from 1 to n such that no element is the average of any two others between which it lies. The brute-force approach would be to generate all possible permutations and check the beautiful array condition for each. However, this is computationally infeasible for even moderate values of n due to the factorial growth of permutations.

To optimize, we need a way to systematically construct such arrays without checking all possibilities. Observing small cases, we notice that separating numbers into odds and evens and recursively building the array helps avoid the forbidden average condition. This is because, for any two numbers of the same parity, their average is always an integer of the same parity, but it falls outside the constructed group. By recursively constructing beautiful arrays of odds and evens and merging them, we can build a beautiful array for any n.

Solution Approach

The algorithm leverages a divide-and-conquer strategy inspired by mathematical induction:

1. Base case: Start with an array containing only 1, which is trivially beautiful.
2. Recursive step: At each stage, for a current beautiful array of size k, generate two new arrays:
   • Odds: For every element x in the current array, add 2*x - 1 if it is ≤ n.
   • Evens: For every element x in the current array, add 2*x if it is ≤ n.
   Concatenate the odds and evens arrays to form the next iteration.
3. Repeat: Continue this process until the array has n elements.
4. Return: The resulting array is guaranteed to be beautiful by construction, as the forbidden average condition is never violated.

This approach is efficient and elegant because it systematically avoids the average condition by construction, without brute-force checking.

Example Walkthrough

Let's walk through the process for n = 5:

1. Start with [1].
2. Generate odds: 1 * 2 - 1 = 1 (≤ 5) → [1]
   Generate evens: 1 * 2 = 2 (≤ 5) → [2]
   Combined: [1, 2]
3. Next iteration:
   • Odds: 1*2-1=1, 2*2-1=3 (both ≤ 5) → [1, 3]
   • Evens: 1*2=2, 2*2=4 (both ≤ 5) → [2, 4]
   Combined: [1, 3, 2, 4]
4. Next iteration:
   • Odds: 1*2-1=1, 3*2-1=5, 2*2-1=3, 4*2-1=7 (only 1, 3, 5 ≤ 5) → [1, 5, 3]
   • Evens: 1*2=2, 3*2=6, 2*2=4, 4*2=8 (only 2, 4 ≤ 5) → [2, 4]
   Combined: [1, 5, 3, 2, 4]
5. Now the array has 5 elements: [1, 5, 3, 2, 4]. This is a valid beautiful array for n = 5.

At each step, the construction guarantees that the forbidden average condition is not met.

Time and Space Complexity

Brute-force Approach: Generating all permutations of n elements and checking each for the beautiful array property would take O(n! * n^2) time, which is infeasible for large n.

Optimized Approach: In the divide-and-conquer construction, each iteration roughly doubles the array size, and each step involves at most O(n) work (mapping and filtering). Therefore, the overall time complexity is O(n \log n), since the number of iterations is O(\log n) and the work per iteration is O(n).

The space complexity is O(n), as we only store the resulting array.

Summary

The beautiful array problem can be elegantly solved using a recursive construction that divides the problem into odds and evens at each level. This guarantees that no element is the average of two others between which it lies, by construction. The approach is efficient, with O(n \log n) time and O(n) space complexity, and avoids brute-force checking entirely. The key insight is leveraging the mathematical properties of odd and even sequences to avoid forbidden averages.