Beautiful Array - Solution & Explanation
Problem Statement
An array nums of length n is beautiful if:
numsis a permutation of the integers in the range[1, n].- For every
0 <= i < j < n, there is no indexkwithi < k < jwhere2 * 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
Approach Overview
Problem 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 1: Divide and Conquer
The divide and conquer approach leverages the idea of placing even indexed numbers on one side and odd indexed numbers on the other. By recursively creating sub-arrays of even and odd indexed numbers, you can ensure no invalid condition occurs. This guarantees each pair (i, j) with i < k < j will never have 2 * nums[k] == nums[i] + nums[j].
The function beautifulArray uses a recursive helper function to construct beautiful arrays. It first handles the base case where n = 1. Then, for the odd indexed and even indexed parts, it recursively computes subarrays, constructing the final array by mapping odd indices to 2*x - 1 and even indices to 2*x, combining these results.
Complexity
Time Complexity: O(n log n) since each step splits the problem in half.
Space Complexity: O(n), due to the recursive calls and the auxiliary space used.
Approach 2: Iterative Construction
Instead of using recursion, you can build the array iteratively. By maintaining arrays for odd and even values, you can loop through to create the beautiful array without recursion. This approach can sometimes offer a different perspective on constructing the solution, focusing on managing even and odd sequences directly in a loop.
The JavaScript function beautifulArray uses a single array initialized with [1] and continuously doubles its size by transforming it into another temporary array twice its size, first filling with odds, then evens.
Code
JavaScript
Java
Complexity
Time Complexity: O(n log n), similar to the recursion method.
Space Complexity: O(n).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Divide and Conquer | Time Complexity: O(n log n) since each step splits the problem in half. |
| Iterative Construction | Time Complexity: O(n log n), similar to the recursion method. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Beautiful Array | Leetcode 932 | Live coding session 🔥🔥🔥 • Coding Decoded • 10,718 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Beautiful Array easy or hard?
Beautiful Array Python/Java solution
How to solve Beautiful Array in O(n)?
What is the best approach for Beautiful Array?
Is Beautiful Array asked at Google/Amazon/Meta?
What data structure is used in Beautiful Array?
What is the time complexity of Beautiful Array?
Ready to solve this problem?
Practice Beautiful Array with our built-in code editor and test cases.
Practice on FleetCode