# Beautiful Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/beautiful-array)
Canonical: https://scaleengineer.com/dsa/problems/beautiful-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array
---
## Problem
An array `nums` of length `n` is **beautiful** if:

* `nums` is a permutation of the integers in the range `[1, n]`.
* For every `0 <= i < j < n`, there is no index `k` with `i < k < j` where `2 * nums[k] == nums[i] + nums[j]`.

Given the integer `n`, return _any **beautiful** array_ `nums` _of length_ `n`. There will be at least one valid answer for the given `n`.

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

# Approaches
## Brute Force by Generating All Permutations
The most straightforward approach is to try every possible arrangement of numbers from 1 to `n`. We can generate all permutations of the array `[1, 2, ..., n]`. For each permutation, we check if it satisfies the 'beautiful' property. The first one we find is a valid answer, as the problem guarantees at least one exists.
**Time:** O(n! * n^3). There are `n!` permutations. For each permutation, we check the beautiful property in O(n^3) time. This is prohibitively slow for the given constraints. · **Space:** O(n) for storing the permutation and for the recursion stack.
**Pros:** Conceptually simple and easy to understand.; Guaranteed to find a solution if one exists.
**Cons:** Extremely inefficient and times out for `n` larger than about 10.
### Explanation
The algorithm first generates a list of numbers from 1 to `n`. It then uses a backtracking algorithm to generate all `n!` permutations of this list. For each generated permutation, a helper function `isBeautiful` is called to verify the property. The `isBeautiful` function iterates through all possible triplets `(i, k, j)` such that `i < k < j`. For each triplet, it checks if `2 * nums[k] == nums[i] + nums[j]`. If this condition is ever met, the array is not beautiful, and the function returns `false`. The first permutation that passes the check is returned as the answer.

```java
class Solution {
    int[] ans;
    public int[] beautifulArray(int n) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        permute(nums, 0);
        return ans;
    }

    private void permute(int[] nums, int start) {
        if (ans != null) return; // Already found a solution
        if (start == nums.length) {
            if (isBeautiful(nums)) {
                ans = nums.clone();
            }
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1);
            swap(nums, start, i); // backtrack
        }
    }

    private boolean isBeautiful(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 2; j < n; j++) {
                for (int k = i + 1; k < j; k++) {
                    if (2 * nums[k] == nums[i] + nums[j]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- Create an array `nums` containing integers from `1` to `n`.
- Implement a backtracking function `generatePermutations(start, nums)`:
  - Base case: If `start == n`, we have a full permutation. Check if it's beautiful using `isBeautiful(nums)`. If it is, store it as the answer and stop.
  - Recursive step: For `i` from `start` to `n-1`:
    - Swap `nums[start]` and `nums[i]`.
    - Call `generatePermutations(start + 1, nums)`.
    - Backtrack: Swap `nums[start]` and `nums[i]` back.
- Implement `isBeautiful(nums)`:
  - For `i` from `0` to `n-1`:
  - For `j` from `i + 2` to `n-1`:
    - For `k` from `i + 1` to `j-1`:
      - If `2 * nums[k] == nums[i] + nums[j]`, return `false`.
  - Return `true`.
- Start the process by calling `generatePermutations(0, nums)`.

## Divide and Conquer using Odd-Even Separation
This approach is based on a key observation about the beautiful array property. The condition `2 * nums[k] == nums[i] + nums[j]` implies that `nums[i]` and `nums[j]` must have the same parity. If we construct an array by placing all odd numbers before all even numbers, the condition can never be met for a pair with one odd and one even number. This divides the problem into two independent subproblems: making the odd part beautiful and the even part beautiful. We can solve these subproblems recursively.
**Time:** O(n log n). The recurrence relation is T(n) = T(ceil(n/2)) + T(floor(n/2)) + O(n), which solves to O(n log n). · **Space:** O(n log n). The recursion depth is O(log n), and at each level, arrays of total size O(n) are created.
**Pros:** Much more efficient than brute force.; It's a clever, constructive algorithm that is guaranteed to work.; The recursive structure is elegant and follows the problem's structure.
**Cons:** The recursive nature can lead to higher space usage compared to an iterative solution due to the call stack.; Slightly less efficient than the iterative approach due to function call overhead.
### Explanation
The problem is reduced to making the subarray of odd numbers beautiful among themselves, and the subarray of even numbers beautiful among themselves. We can leverage a useful mapping property: if an array `A` is beautiful, then an affine transformation `k*A + c` (element-wise operation) is also beautiful. 

The set of odd numbers in `[1, ..., n]` is `{1, 3, 5, ...}` which can be generated from `{1, 2, 3, ...}` by the transformation `2x - 1`. Similarly, the set of even numbers `{2, 4, 6, ...}` can be generated by `2x`. 

This leads to a recursive solution:
1. To get a beautiful array for `n`, we first find beautiful arrays for `ceil(n/2)` and `floor(n/2)`. 
2. We take the beautiful array for `ceil(n/2)` and transform it via `2x - 1` to get a beautiful arrangement of all odd numbers up to `n`.
3. We take the beautiful array for `floor(n/2)` and transform it via `2x` to get a beautiful arrangement of all even numbers up to `n`.
4. Concatenating these two results gives a beautiful array for `n`.

```java
class Solution {
    public int[] beautifulArray(int n) {
        if (n == 1) {
            return new int[]{1};
        }
        
        // Divide
        int[] odds = beautifulArray((n + 1) / 2); // ceil(n/2)
        int[] evens = beautifulArray(n / 2);      // floor(n/2)
        
        // Conquer
        int[] result = new int[n];
        int index = 0;
        
        // Map to odd numbers
        for (int x : odds) {
            result[index++] = 2 * x - 1;
        }
        
        // Map to even numbers
        for (int x : evens) {
            result[index++] = 2 * x;
        }
        
        return result;
    }
}
```
### Algorithm
- Base Case: If `n = 1`, return `[1]`.
- Recursively call the function to get the beautiful array for `(n + 1) / 2` (ceiling of n/2), let's call it `odds_res`.
- Recursively call the function to get the beautiful array for `n / 2` (floor of n/2), let's call it `evens_res`.
- Create a new result array of size `n`.
- Iterate through `odds_res`. For each element `x`, calculate `2*x - 1` and add it to the result array.
- Iterate through `evens_res`. For each element `y`, calculate `2*y` and add it to the result array.
- Return the result array.

## Iterative Bottom-Up Construction
The recursive divide-and-conquer approach can be transformed into an iterative, bottom-up solution. We can start with a base beautiful array `[1]` and iteratively expand it to build a beautiful array for `n`. The logic remains the same: in each step, we generate new odd and even numbers from the current beautiful sequence, ensuring the beautiful property is maintained at a larger scale.
**Time:** O(n). The size of the list `res` grows, but the total number of element operations across all iterations of the while loop is proportional to `1 + 2 + 4 + ... + k` where `k` is approximately `n`. This sum is O(n). · **Space:** O(n). We need space to store the current list `res` and the temporary list `temp`, both of which can grow up to size `n`.
**Pros:** Most efficient solution in terms of both time and space.; Avoids recursion overhead and potential stack overflow for very large `n` (though not an issue with the given constraints).
**Cons:** The logic might be slightly less intuitive to grasp initially compared to the recursive version.
### Explanation
We start with a list `res` containing just the number `1`, which is a beautiful array for `n=1`. We then enter a loop that continues as long as the size of our list `res` is less than `n`. Inside the loop, we create a new temporary list `temp`. We iterate through the current `res` list. For each number `x` in `res`, we generate a potential odd number `2*x - 1` and a potential even number `2*x`. We first generate all valid odd numbers (those `<= n`) and add them to `temp`. Then, we generate all valid even numbers and add them to `temp`. After processing all numbers in the current `res`, `temp` will contain a new, larger beautiful sequence. We update `res` to be `temp` and repeat. The loop terminates when the list contains `n` elements.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] beautifulArray(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(1);
        
        while (res.size() < n) {
            List<Integer> temp = new ArrayList<>();
            // Generate odd numbers
            for (int x : res) {
                if (2 * x - 1 <= n) {
                    temp.add(2 * x - 1);
                }
            }
            // Generate even numbers
            for (int x : res) {
                if (2 * x <= n) {
                    temp.add(2 * x);
                }
            }
            res = temp;
        }
        
        int[] resultArr = new int[n];
        for (int i = 0; i < n; i++) {
            resultArr[i] = res.get(i);
        }
        return resultArr;
    }
}
```
### Algorithm
- Initialize a list `res` with the element `1`.
- While the size of `res` is less than `n`:
  - Create an empty list `temp`.
  - For each element `x` in `res`:
    - If `2 * x - 1 <= n`, add `2 * x - 1` to `temp`.
  - For each element `x` in `res`:
    - If `2 * x <= n`, add `2 * x` to `temp`.
  - Replace `res` with `temp`.
- Convert the final list `res` to an integer array and return it.

# Solutions
### Java

```java
class Solution {
public
  int[] beautifulArray(int n) {
    if (n == 1) {
      return new int[]{1};
    }
    int[] left = beautifulArray((n + 1) >> 1);
    int[] right = beautifulArray(n >> 1);
    int[] ans = new int[n];
    int i = 0;
    for (int x : left) {
      ans[i++] = x * 2 - 1;
    }
    for (int x : right) {
      ans[i++] = x * 2;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> beautifulArray(int n) {
    if (n == 1)
      return {1};
    vector<int> left = beautifulArray((n + 1) >> 1);
    vector<int> right = beautifulArray(n >> 1);
    vector<int> ans(n);
    int i = 0;
    for (int &x : left)
      ans[i++] = x * 2 - 1;
    for (int &x : right)
      ans[i++] = x * 2;
    return ans;
  }
};

```

### Python

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

```