Is Beautiful Array easy or hard?

Beautiful Array is rated Medium on LeetCode with an acceptance rate around 69%. The implementation itself is simple once the parity insight is discovered, but recognizing the mathematical pattern that guarantees the constraint is what makes the problem challenging.

Beautiful Array Python/Java solution

Python and C++ implementations commonly use a recursive divide-and-conquer approach that builds odd and even transformed subarrays. Java and JavaScript solutions often implement the iterative expansion version, starting from [1] and repeatedly generating valid odd and even values until reaching size n.

How to solve Beautiful Array in O(n)?

Build the array using parity transformations. Start with [1], repeatedly create two lists: odd numbers using 2*x-1 and even numbers using 2*x. Append values that remain within the range 1..n. Because these transformations preserve the beautiful property, the final array is valid and the total work is linear.

What is the best approach for Beautiful Array?

The optimal approach uses a divide and conquer construction based on parity. Start with a small beautiful array and transform it into odd values (2*x-1) and even values (2*x). Because odd and even transformations preserve the "no average" constraint, combining them produces a valid array of size n. This method runs in O(n) time and O(n) space.

Is Beautiful Array asked at Google/Amazon/Meta?

Beautiful Array appears in interview preparation sets for companies like Google, Amazon, and Meta because it tests mathematical insight and constructive algorithms. The problem evaluates whether you can discover structural patterns rather than brute-force search.

What data structure is used in Beautiful Array?

The solution primarily uses arrays or lists to store and construct the permutation. The algorithm repeatedly transforms and appends elements using simple arithmetic operations, so no complex data structures such as heaps or hash maps are required.

What is the time complexity of Beautiful Array?

The optimal construction runs in O(n) time and O(n) space. Each number from 1 to n is generated through a constant number of arithmetic transformations and appended to the result array once. No nested iteration over the array is required.

Description Solution Video 8:40

932. Beautiful Array

Medium70.7% acceptance4 companies

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

Asked at 4 companies

Google Amazon Meta Bloomberg

Topics

8:40

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def beautifulArray(self, n: int) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.Solution