Sponsored
Sponsored
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].
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.
1def beautifulArray(n):
2 def helper(n):
3 if n == 1:
4 return [1]
5 odd = helper((n + 1) // 2)
6 even = helper(n // 2)
7 return [2 * x - 1 for x in odd] + [2 * x for x in even]
8 return helper(n)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.
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.
Time Complexity: O(n log n), similar to the recursion method.
Space Complexity: O(n).
1function beautifulArray(n) {
2 let result 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.