Beautiful Array

Problem Statement

An array nums of a specific length n is considered beautiful if it meets two primary conditions:

• The array is a permutation of the integers 1 to n. In other words, nums contains all integers from 1 up to n exactly once.
• For any pair of indices i and j such that 0 <= i < j < n, no intermediate index k (where i < k < j) satisfies the equation 2 * nums[k] == nums[i] + nums[j]. This requirement ensures that no middle element in the array is the strict average of two other elements that are on either side of it.

Given the integer n, the task is to find and return any beautiful array nums of length n. There will always be at least one valid configuration for the specified n.

Examples

Example 1

Input:

n = 4

Output:

[2,1,4,3]

Example 2

Input:

n = 5

Output:

[3,1,2,5,4]

Constraints

• 1 <= n <= 1000

Approach and Intuition

Understanding the approach to generate a beautiful array can be facilitated by the provided examples. Here's a breakdown based on the conditions:

Examples

Example 1

Input:

n = 4

Output:

[2,1,4,3]

Example 2

Input:

n = 5

Output:

[3,1,2,5,4]

Constraints

• 1 <= n <= 1000

Approach

The approach to constructing a beautiful array can be achieved by leveraging the divide and conquer strategy. Here's a breakdown of the steps:

1. Start by considering two separate sequences, one containing all odd numbers and the other containing all even numbers within the range [1, n].
2. Recursively apply the method to each sequence. A smaller instance of a beautiful array of odds or evens can itself be beautiful.
3. Concatenate the results from the odd and even sequences to build the full beautiful array. This approach works because any conditions that might disrupt the "beautiful" arrangement are inherently avoided by separating odds and evens—the sums of an even and an odd number can never be exactly twice another number completely from odd or even subsets.

• For instance, if you split an array into [odd numbers] and [even numbers], the condition 2 * nums[k] == nums[i] + nums[j] gets inherently sidestepped. Owing to the nature of evenness and oddness, adding two odds or two evens results in an even number, while doubling any single element from one set would always result in an even number too, hence the equation cannot be satisfied.

Intuition

• Permuting and checking every combination until the conditions are satisfied would be computationally expensive, especially as n grows.
• The separation technique ensures there can be no k for which the condition 2 * nums[k] == nums[i] + nums[j] will hold, given how summing and doubling works within odds and evens.
• The method is not just efficient but guarantees the fulfillment of conditions without needing extensive checking after array construction.

Solutions

class Solution {
    Map<Integer, int[]> cache;
    
    public int[] beautifulArray(int N) {
        cache = new HashMap<>();
        return generateArray(N);
    }
    
    public int[] generateArray(int N) {
        if (cache.containsKey(N))
            return cache.get(N);
    
        int[] result = new int[N];
        if (N == 1) {
            result[0] = 1;
        } else {
            int idx = 0;
            for (int element : generateArray((N + 1) / 2)) // odd numbers
                result[idx++] = 2 * element - 1;
            for (int element : generateArray(N / 2)) // even numbers
                result[idx++] = 2 * element;
        }
        cache.put(N, result);
        return result;
    }
}