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 <= 1000The 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.
C++
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.
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.
Java
Time Complexity: O(n log n), similar to the recursion method.
Space Complexity: O(n).
| 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. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,144 views views
Watch 9 more video solutions →Practice Beautiful Array with our built-in code editor and test cases.
Practice on FleetCode