932. Beautiful Array
Problem Description
We need to construct a beautiful array
for a given integer n
. An array is defined to be beautiful if it satisfies two conditions:
- The array is a permutation of the integers in the range
[1, n]
. That means it contains all the integers from 1 ton
, each one exactly once. - For every pair of indices
0 <= i < j < n
, there is no indexk
such thati < k < j
and2 * nums[k] == nums[i] + nums[j]
. In other words, no element is the average of any other two distinct elements not directly next to it.
Our goal is to find at least one such array that meets these criteria.
Intuition
The problem might seem complex at first because the second condition appears to require checking many possible combinations of triplet indices. However, there is a neat recursive approach that can simplify this problem significantly, and it's based on the following observations:
- If an array is beautiful, then so are its subarrays. So if we have a beautiful array, any subarray extracted from it will also fulfill the beauty condition.
- If we divide the array into odd and even elements, none of the even elements can be the average of two odd elements, and vice versa. This is because the sum of two odd numbers is an even number, and the average will also be an odd number. Similarly, the average of two even numbers is an even number. Since we don't mix odds and evens, we don't need to worry about condition 2 when merging them back together.
Leveraging these insights, the solution employs divide and conquer strategy, where it recursively generates the left half of the array with odd elements and the right half with even elements. The array generated from the left recursive call is comprised of all odds (by multiplying by 2 and then subtracting 1), and the array from the right recursive call is comprised of all evens (by multiplying by 2). Combining these two beautiful arrays yields a new beautiful array.
Here are the steps of the solution approach:
- Define a base case for the recursive function: when
n == 1
, return the array[1]
because it trivially satisfies both conditions. - For
n > 1
, make two recursive calls:- The first call is for
((n + 1) >> 1)
, which ensures we cover all numbers whenn
is odd. - The second call is for
(n >> 1)
, which is straightforward since we are dividingn
by 2.
- The first call is for
- Convert the left array into odd elements and the right array into even elements.
- Return the concatenation of the left and right arrays, knowing that they are both beautiful and won’t violate conditions when merged, due to the aforementioned observations.
When going step by step through this recursive approach, we are able to build a beautiful array that fulfills the problem's requirements.
Learn more about Math and Divide and Conquer patterns.
Solution Approach
The solution takes advantage of divide and conquer strategy along with recursion. Here’s how the implementation is carried out step-by-step, referring to the code provided as a reference:
-
Base Case:
- The recursion starts with the simplest scenario, which is when
n == 1
. In this case, the function just returns a single-element array containing only[1]
since it's trivially beautiful.
- The recursion starts with the simplest scenario, which is when
-
Divide Step:
- The array needs to be split into two, one with the odds and one with the evens. The division is not made by slicing the existing array but by reducing the problem size and calling the
beautifulArray
function recursively. - The function is called twice recursively, first for the left side with
((n + 1) >> 1)
, and second for the right side with(n >> 1)
.>>
is the bitwise right shift operator which effectively divides the number by 2, and in the case of((n + 1) >> 1)
, it ensures that we account for an additional element in casen
is odd.
- The array needs to be split into two, one with the odds and one with the evens. The division is not made by slicing the existing array but by reducing the problem size and calling the
-
Conquer Step:
- The left and right arrays are generated by the recursive calls and are guaranteed to be beautiful by the recursive hypothesis.
- The next step is to adjust the values for both arrays:
- For the left array, each element is made odd by the transformation
x * 2 - 1
- For the right array, each element is made even by the transformation
x * 2
- For the left array, each element is made odd by the transformation
-
Combine Step:
- As per the mathematical observations, the even-indexed elements and odd-indexed elements do not interfere with the beauty condition when merged.
- With this assurance, the function combines (
left + right
) the two arrays which have been separately ensured to be beautiful. Due to the observation that the even elements cannot be the average of two odd elements, this ensures that the combined array is also beautiful.
-
Data Structures and Patterns:
- The main data structure used is the array or list in Python.
- The pattern used is divide and conquer, which simplifies the problem by breaking it down into smaller subproblems, in this case, creating smaller "beautiful" arrays and then combining them together.
The solution does not require the use of any complex algorithms or additional data structures, relying instead on the mathematical properties of the numbers involved and a straightforward recursive strategy. By ensuring that each recursive call returns a beautiful array, the final result by concatenation is also guaranteed to be a beautiful array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach using the recursive divide and conquer strategy for constructing a beautiful array. We will use n = 5
for our example.
-
Starting Point Since
n
is 5, it is greater than 1. We need to make two recursive calls to handle the odds and the evens separately. -
First Recursive Call (Odds)
-
We calculate
((n + 1) >> 1)
which in this case is((5 + 1) >> 1)
=3
. -
The recursive call for
beautifulArray(3)
will now be made. -
Inside this call, since
3 > 1
, two more recursive calls are made:- First for
beautifulArray(((3 + 1) >> 1))
which isbeautifulArray(2)
. - Second for
beautifulArray((3 >> 1))
which isbeautifulArray(1)
.
- First for
-
For
beautifulArray(2)
, we will have another set of recursive calls for 1 (beautifulArray(1)), which just returns[1]
. The odd transformationx * 2 - 1
for[1]
will give us[1]
. -
Since
beautifulArray(1)
is the base case, it returns[1]
as mentioned. The even transformationx * 2
will give us[2]
. -
After the transformations and combining the results, we get the left part as
[1, 2]
.
-
-
Second Recursive Call (Evens)
-
Now we calculate
(n >> 1)
which is(5 >> 1)
=2
. -
The recursive call for
beautifulArray(2)
will now be made. -
Inside this call, since
2 > 1
, two more recursive calls are made:- First for
beautifulArray(((2 + 1) >> 1))
which isbeautifulArray(1)
and we get[1]
. The odd transformation isx * 2 - 1
which will give us[1]
. - Second for
beautifulArray((2 >> 1))
which isbeautifulArray(1)
and we also get[1]
. The even transformation isx * 2
which will give us[2]
.
- First for
-
After the transformations and combining the results, we get the right part as
[3, 4]
.
-
-
Combine Step
-
Now we have our left and right arrays which are
[1, 2]
and[3, 4]
respectively. -
We need to adjust values for both to ensure odds and evens:
- For the left part, we apply the odd transformation:
[1 * 2 - 1, 2 * 2 - 1]
which results in[1, 3]
. - For the right part, we apply the even transformation:
[3 * 2, 4 * 2]
which results in[6, 8]
.
- For the left part, we apply the odd transformation:
-
However, notice that after applying transformations, elements in the right part exceed
n = 5
. We should only include elements up ton
, which means we take the elements[2, 4]
([6, 8]
is out of the range[1, n]
).
-
-
Concatenation
- The left and right arrays are combined to form the beautiful array:
[1, 3] + [2, 4]
which gives us[1, 3, 2, 4]
.
- The left and right arrays are combined to form the beautiful array:
-
Final Adjustment
- We still need to include all integers from 1 to
n
, which means we need to insert the missing element5
. Since5
is an odd number, it can seamlessly be added to the end of our existing array without violating the beautiful array conditions. - The final beautiful array is:
[1, 3, 2, 4, 5]
.
- We still need to include all integers from 1 to
Thus, using the divide and conquer approach and ensuring that we only combine elements that won't violate the beautiful array condition, we've constructed a beautiful array for n = 5
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def beautifulArray(self, n: int) -> List[int]:
5 # Base case: if n is 1, return an array containing just the number 1
6 if n == 1:
7 return [1]
8
9 # Recursively generate the left half of the array with the next odd n
10 left_half = self.beautifulArray((n + 1) // 2)
11 # Recursively generate the right half of the array with the next even n
12 right_half = self.beautifulArray(n // 2)
13
14 # Double each element of the left half and subtract 1 to keep all elements odd
15 left_half = [element * 2 - 1 for element in left_half]
16 # Double each element of the right half to keep all elements even
17 right_half = [element * 2 for element in right_half]
18
19 # Combine the left and right halves to form the beautiful array
20 return left_half + right_half
21
1class Solution {
2 public int[] beautifulArray(int n) {
3 // Base case: if the array size is 1, return an array with a single element 1
4 if (n == 1) {
5 return new int[] {1};
6 }
7
8 // Recursively call the function for the first half, rounded up
9 int[] leftHalf = beautifulArray((n + 1) >> 1);
10
11 // Recursively call the function for the second half
12 int[] rightHalf = beautifulArray(n >> 1);
13
14 // Create an array to hold the beautiful array of size n
15 int[] result = new int[n];
16
17 int index = 0; // Initialize the index for the result array
18
19 // Fill the result array with odd numbers by manipulating the left half
20 for (int element : leftHalf) {
21 result[index++] = element * 2 - 1;
22 }
23
24 // Fill the result array with even numbers by manipulating the right half
25 for (int element : rightHalf) {
26 result[index++] = element * 2;
27 }
28
29 // Return the compiled beautiful array
30 return result;
31 }
32}
33
1class Solution {
2public:
3 vector<int> beautifulArray(int n) {
4 // Base case - if n is 1, return an array containing just the number 1
5 if (n == 1) return {1};
6
7 // Recursive call to construct the left half of the beautiful array
8 // for the numbers less than or equal to (n + 1) / 2
9 vector<int> leftHalf = beautifulArray((n + 1) >> 1);
10
11 // Recursive call to construct the right half of the beautiful array
12 // for the numbers less than or equal to n / 2
13 vector<int> rightHalf = beautifulArray(n >> 1);
14
15 // Initialize the beautiful array for n elements
16 vector<int> result(n);
17 int currentIndex = 0;
18
19 // Populate the beautiful array with odd numbers by manipulating elements of the left half
20 for (int& element : leftHalf) {
21 result[currentIndex++] = element * 2 - 1;
22 }
23
24 // Populate the rest of the beautiful array with even numbers by manipulating elements of the right half
25 for (int& element : rightHalf) {
26 result[currentIndex++] = element * 2;
27 }
28
29 // Return the completed beautiful array
30 return result;
31 }
32};
33
1function beautifulArray(n: number): number[] {
2 // Base case - if n is 1, return an array containing just the number 1
3 if (n === 1) return [1];
4
5 // Recursive call to construct the left half of the beautiful array
6 // for numbers less than or equal to (n + 1) / 2
7 let leftHalf: number[] = beautifulArray(Math.ceil(n / 2));
8
9 // Recursive call to construct the right half of the beautiful array
10 // for numbers less than or equal to n / 2
11 let rightHalf: number[] = beautifulArray(Math.floor(n / 2));
12
13 // Initialize the beautiful array for n elements
14 let result: number[] = new Array(n);
15 let currentIndex: number = 0;
16
17 // Populate the beautiful array with odd numbers by manipulating elements of the left half
18 for (let element of leftHalf) {
19 result[currentIndex++] = element * 2 - 1;
20 }
21
22 // Populate the rest of the beautiful array with even numbers by manipulating elements of the right half
23 for (let element of rightHalf) {
24 result[currentIndex++] = element * 2;
25 }
26
27 // Return the completed beautiful array
28 return result;
29}
30
Time and Space Complexity
The given Python code generates a beautiful array for a given integer n
. A beautiful array is an array where for every i < j < k
, A[i] * A[k] != 2 * A[j]
. The approach is to recursively split the problem into two halves: generating a beautiful array for the odd numbers and for the even numbers, and then combining these arrays.
Time Complexity
The recursion happens by dividing the problem size roughly in half at each step: once for numbers > n/2
that will be twiced and decreased by one (odd numbers) and once for numbers <= n/2
that will be just twiced (even numbers). If T(n)
represents the time complexity of the beautifulArray
function, this gives us a recurrence relation similar to the one for the merge sort algorithm, which is T(n) = 2 * T(n/2) + O(n)
.
At each level of recursion, we perform an operation proportional to n
(specifically, multiplying and unit decrementing/incrementing each element in the arrays). Since the number of levels of the recursion would be O(logn)
, multiplying numbers at each level gives us O(nlogn)
.
Therefore, the overall time complexity of this algorithm is O(nlogn)
.
Space Complexity
For the space complexity, each recursive call requires its own space to store left and right subarrays, which are of size n
. The space needed will be the height of the recursion tree, which is O(logn)
, times the largest width of the tree, which is O(n)
at the bottom level.
This leads to a space complexity of O(nlogn)
as well, because we have to consider the space used by all levels of the recursion stack until the base case is reached.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.