Watch 10 video solutions for Beautiful Array, a medium level problem involving Array, Math, Divide and Conquer. This walkthrough by Coding Decoded has 10,155 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
An array nums of length n is beautiful if:
nums is a permutation of the integers in the range [1, n].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 <= 1000Problem Overview: Build a permutation of numbers from 1..n such that for any i < j, there is no index k between them where A[k] * 2 = A[i] + A[j]. In other words, no element should be the average of two elements that appear on both sides of it.
Approach 1: Divide and Conquer Construction (O(n) time, O(n) space)
The key observation comes from number parity. If you start with a valid beautiful array A, transforming it into odd numbers 2*x - 1 and even numbers 2*x preserves the property that no element becomes the average of two others. This allows you to recursively construct two smaller beautiful arrays and combine them: first all transformed odd elements, then all transformed even elements. Because odd and even groups cannot produce the forbidden average across groups, the combined array remains valid.
The divide-and-conquer process keeps splitting the problem until size 1. Each recursive layer maps values using simple arithmetic transformations and concatenates results. Every number from 1..n appears exactly once, and each element is generated a constant number of times. The result is a linear-time construction. This approach highlights a clever property of parity and works naturally with divide and conquer and math reasoning.
Approach 2: Iterative Construction with Expansion (O(n) time, O(n) space)
An iterative version builds the array step by step instead of recursion. Start with [1] as the smallest beautiful array. At each step, generate two candidate lists: odd transformations 2*x - 1 and even transformations 2*x. Append values that stay within the range <= n. Because the odd transformation is applied before the even transformation, the resulting sequence maintains the same invariant as the recursive solution.
The iteration continues until the list reaches size n. Each round roughly doubles the candidate size before filtering values greater than n. The arithmetic transformation ensures the average condition never appears. This method is often easier to implement in languages where recursion overhead is undesirable. It relies mainly on sequential array operations and fits naturally into problems categorized under array construction.
Recommended for interviews: The divide-and-conquer insight is what interviewers typically look for. Showing that parity transformations preserve the "no average" property demonstrates strong mathematical reasoning. The iterative version is equally efficient and sometimes cleaner in code, but explaining the divide-and-conquer idea first shows deeper understanding of why the construction works.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer Construction | O(n) | O(n) | Best for interviews when explaining the parity insight and recursive structure. |
| Iterative Expansion | O(n) | O(n) | Preferred when avoiding recursion or implementing a simple loop-based array construction. |