Beautiful Array
MedPrompt
An array nums of length n is beautiful if:
numsis a permutation of the integers in the range[1, n].- For every
0 <= i < j < n, there is no indexkwithi < k < jwhere2 * 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
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to try every possible arrangement of numbers from 1 to n. We can generate all permutations of the array [1, 2, ..., n]. For each permutation, we check if it satisfies the 'beautiful' property. The first one we find is a valid answer, as the problem guarantees at least one exists.
Algorithm
- Create an array
numscontaining integers from1ton. - Implement a backtracking function
generatePermutations(start, nums):- Base case: If
start == n, we have a full permutation. Check if it's beautiful usingisBeautiful(nums). If it is, store it as the answer and stop. - Recursive step: For
ifromstartton-1:- Swap
nums[start]andnums[i]. - Call
generatePermutations(start + 1, nums). - Backtrack: Swap
nums[start]andnums[i]back.
- Swap
- Base case: If
- Implement
isBeautiful(nums):- For
ifrom0ton-1: - For
jfromi + 2ton-1:- For
kfromi + 1toj-1:- If
2 * nums[k] == nums[i] + nums[j], returnfalse.
- If
- For
- Return
true.
- For
- Start the process by calling
generatePermutations(0, nums).
Walkthrough
The algorithm first generates a list of numbers from 1 to n. It then uses a backtracking algorithm to generate all n! permutations of this list. For each generated permutation, a helper function isBeautiful is called to verify the property. The isBeautiful function iterates through all possible triplets (i, k, j) such that i < k < j. For each triplet, it checks if 2 * nums[k] == nums[i] + nums[j]. If this condition is ever met, the array is not beautiful, and the function returns false. The first permutation that passes the check is returned as the answer.
class Solution { int[] ans; public int[] beautifulArray(int n) { int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = i + 1; } permute(nums, 0); return ans; } private void permute(int[] nums, int start) { if (ans != null) return; // Already found a solution if (start == nums.length) { if (isBeautiful(nums)) { ans = nums.clone(); } return; } for (int i = start; i < nums.length; i++) { swap(nums, start, i); permute(nums, start + 1); swap(nums, start, i); // backtrack } } private boolean isBeautiful(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 2; j < n; j++) { for (int k = i + 1; k < j; k++) { if (2 * nums[k] == nums[i] + nums[j]) { return false; } } } } return true; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Complexity
Time
O(n! * n^3). There are `n!` permutations. For each permutation, we check the beautiful property in O(n^3) time. This is prohibitively slow for the given constraints.
Space
O(n) for storing the permutation and for the recursion stack.
Trade-offs
Pros
Conceptually simple and easy to understand.
Guaranteed to find a solution if one exists.
Cons
Extremely inefficient and times out for
nlarger than about 10.
This approach is based on a key observation about the beautiful array property. The condition 2 * nums[k] == nums[i] + nums[j] implies that nums[i] and nums[j] must have the same parity. If we construct an array by placing all odd numbers before all even numbers, the condition can never be met for a pair with one odd and one even number. This divides the problem into two independent subproblems: making the odd part beautiful and the even part beautiful. We can solve these subproblems recursively.
Algorithm
- Base Case: If
n = 1, return[1]. - Recursively call the function to get the beautiful array for
(n + 1) / 2(ceiling of n/2), let's call itodds_res. - Recursively call the function to get the beautiful array for
n / 2(floor of n/2), let's call itevens_res. - Create a new result array of size
n. - Iterate through
odds_res. For each elementx, calculate2*x - 1and add it to the result array. - Iterate through
evens_res. For each elementy, calculate2*yand add it to the result array. - Return the result array.
Walkthrough
The problem is reduced to making the subarray of odd numbers beautiful among themselves, and the subarray of even numbers beautiful among themselves. We can leverage a useful mapping property: if an array A is beautiful, then an affine transformation k*A + c (element-wise operation) is also beautiful.
The set of odd numbers in [1, ..., n] is {1, 3, 5, ...} which can be generated from {1, 2, 3, ...} by the transformation 2x - 1. Similarly, the set of even numbers {2, 4, 6, ...} can be generated by 2x.
This leads to a recursive solution:
- To get a beautiful array for
n, we first find beautiful arrays forceil(n/2)andfloor(n/2). - We take the beautiful array for
ceil(n/2)and transform it via2x - 1to get a beautiful arrangement of all odd numbers up ton. - We take the beautiful array for
floor(n/2)and transform it via2xto get a beautiful arrangement of all even numbers up ton. - Concatenating these two results gives a beautiful array for
n.
class Solution { public int[] beautifulArray(int n) { if (n == 1) { return new int[]{1}; } // Divide int[] odds = beautifulArray((n + 1) / 2); // ceil(n/2) int[] evens = beautifulArray(n / 2); // floor(n/2) // Conquer int[] result = new int[n]; int index = 0; // Map to odd numbers for (int x : odds) { result[index++] = 2 * x - 1; } // Map to even numbers for (int x : evens) { result[index++] = 2 * x; } return result; }}Complexity
Time
O(n log n). The recurrence relation is T(n) = T(ceil(n/2)) + T(floor(n/2)) + O(n), which solves to O(n log n).
Space
O(n log n). The recursion depth is O(log n), and at each level, arrays of total size O(n) are created.
Trade-offs
Pros
Much more efficient than brute force.
It's a clever, constructive algorithm that is guaranteed to work.
The recursive structure is elegant and follows the problem's structure.
Cons
The recursive nature can lead to higher space usage compared to an iterative solution due to the call stack.
Slightly less efficient than the iterative approach due to function call overhead.
The recursive divide-and-conquer approach can be transformed into an iterative, bottom-up solution. We can start with a base beautiful array [1] and iteratively expand it to build a beautiful array for n. The logic remains the same: in each step, we generate new odd and even numbers from the current beautiful sequence, ensuring the beautiful property is maintained at a larger scale.
Algorithm
- Initialize a list
reswith the element1. - While the size of
resis less thann:- Create an empty list
temp. - For each element
xinres:- If
2 * x - 1 <= n, add2 * x - 1totemp.
- If
- For each element
xinres:- If
2 * x <= n, add2 * xtotemp.
- If
- Replace
reswithtemp.
- Create an empty list
- Convert the final list
resto an integer array and return it.
Walkthrough
We start with a list res containing just the number 1, which is a beautiful array for n=1. We then enter a loop that continues as long as the size of our list res is less than n. Inside the loop, we create a new temporary list temp. We iterate through the current res list. For each number x in res, we generate a potential odd number 2*x - 1 and a potential even number 2*x. We first generate all valid odd numbers (those <= n) and add them to temp. Then, we generate all valid even numbers and add them to temp. After processing all numbers in the current res, temp will contain a new, larger beautiful sequence. We update res to be temp and repeat. The loop terminates when the list contains n elements.
import java.util.ArrayList;import java.util.List; class Solution { public int[] beautifulArray(int n) { List<Integer> res = new ArrayList<>(); res.add(1); while (res.size() < n) { List<Integer> temp = new ArrayList<>(); // Generate odd numbers for (int x : res) { if (2 * x - 1 <= n) { temp.add(2 * x - 1); } } // Generate even numbers for (int x : res) { if (2 * x <= n) { temp.add(2 * x); } } res = temp; } int[] resultArr = new int[n]; for (int i = 0; i < n; i++) { resultArr[i] = res.get(i); } return resultArr; }}Complexity
Time
O(n). The size of the list `res` grows, but the total number of element operations across all iterations of the while loop is proportional to `1 + 2 + 4 + ... + k` where `k` is approximately `n`. This sum is O(n).
Space
O(n). We need space to store the current list `res` and the temporary list `temp`, both of which can grow up to size `n`.
Trade-offs
Pros
Most efficient solution in terms of both time and space.
Avoids recursion overhead and potential stack overflow for very large
n(though not an issue with the given constraints).
Cons
The logic might be slightly less intuitive to grasp initially compared to the recursive version.
Solutions
Solution
class Solution {public int[] beautifulArray(int n) { if (n == 1) { return new int[]{1}; } int[] left = beautifulArray((n + 1) >> 1); int[] right = beautifulArray(n >> 1); int[] ans = new int[n]; int i = 0; for (int x : left) { ans[i++] = x * 2 - 1; } for (int x : right) { ans[i++] = x * 2; } return ans; }}class Solution {public: vector<int> beautifulArray(int n) { if (n == 1) return {1}; vector<int> left = beautifulArray((n + 1) >> 1); vector<int> right = beautifulArray(n >> 1); vector<int> ans(n); int i = 0; for (int &x : left) ans[i++] = x * 2 - 1; for (int &x : right) ans[i++] = x * 2; return ans; }};class Solution: def beautifulArray(self, n: int) -> List[int]: if n == 1: return [1] left = self . beautifulArray((n + 1) >> 1) right = self . beautifulArray(n >> 1) left = [x * 2 - 1 for x in left] right = [x * 2 for x in right] return left + rightVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.