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.
1#include <vector>
2using namespace std;
3
4vector<int> beautifulArray(int n) {
5 if (n == 1) return {1};
6 vector<int> ans(n);
7 vector<int> odd = beautifulArray((n + 1) / 2);
8 vector<int> even = beautifulArray(n / 2);
9 for (int i = 0; i < odd.size(); ++i) ans[i] = 2 * odd[i] - 1;
10 for (int i = 0; i < even.size(); ++i) ans[i + odd.size()] = 2 * even[i];
11 return ans;
12}In the C++ solution, a similar recursive approach is used. Through vector concatenation of the results of the odd and even subproblem solutions, a beautiful array for any n is dynamically constructed.
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).
1import java.util.ArrayList;
2import
The Java method uses an iterative approach with an ArrayList to construct the final beautiful array incrementally. It builds the results and transfers them into an integer array to produce the final output.