In this guide, you will get 932. Beautiful Array LeetCode Solution with the best time and space complexity. The solution to Beautiful Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
932. Beautiful Array LeetCode Solution in C++
class Solution {
public:
vector<int> beautifulArray(int n) {
vector<int> arr(n);
iota(arr.begin(), arr.end(), 1);
divide(arr, 0, n - 1, 1);
return arr;
}
private:
void divide(vector<int>& arr, int l, int r, int mask) {
if (l >= r)
return;
const int m = partition(arr, l, r, mask);
divide(arr, l, m, mask << 1);
divide(arr, m + 1, r, mask << 1);
}
int partition(vector<int>& arr, int l, int r, int mask) {
int nextSwapped = l;
for (int i = l; i <= r; ++i)
if (arr[i] & mask)
swap(arr[i], arr[nextSwapped++]);
return nextSwapped - 1;
}
}; /* code provided by PROGIEZ */
932. Beautiful Array LeetCode Solution in Java
class Solution {
public int[] beautifulArray(int n) {
int[] arr = new int[n];
for (int i = 0; i < n; ++i)
arr[i] = i + 1;
divide(arr, 0, n - 1, 1);
return arr;
}
private void divide(int[] arr, int l, int r, int mask) {
if (l >= r)
return;
final int m = partition(arr, l, r, mask);
divide(arr, l, m, mask << 1);
divide(arr, m + 1, r, mask << 1);
}
private int partition(int[] arr, int l, int r, int mask) {
int nextSwapped = l;
for (int i = l; i <= r; ++i)
if ((arr[i] & mask) > 0)
swap(arr, i, nextSwapped++);
return nextSwapped - 1;
}
private void swap(int[] arr, int i, int j) {
final int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} // code provided by PROGIEZ
932. Beautiful Array LeetCode Solution in Python
class Solution:
def beautifulArray(self, n: int) -> list[int]:
arr = [i for i in range(1, n + 1)]
def partition(l: int, r: int, mask: int) -> int:
nextSwapped = l
for i in range(l, r + 1):
if arr[i] & mask:
arr[i], arr[nextSwapped] = arr[nextSwapped], arr[i]
nextSwapped += 1
return nextSwapped - 1
def divide(l: int, r: int, mask: int) -> None:
if l >= r:
return
m = partition(l, r, mask)
divide(l, m, mask << 1)
divide(m + 1, r, mask << 1)
divide(0, n - 1, 1)
return arr # code by PROGIEZ
