Beautiful Array - Problem

An array nums of length n is beautiful if:

  • 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.

Input & Output

Example 1 — Small Case
$ Input: n = 4
Output: [1,3,2,4]
💡 Note: This is a beautiful array because for any i < j, there's no k with i < k < j where 2*nums[k] = nums[i] + nums[j]. For instance, checking all triplets: no middle element equals the average of two others.
Example 2 — Base Case
$ Input: n = 1
Output: [1]
💡 Note: Single element array is always beautiful since there are no triplets to violate the condition.
Example 3 — Larger Array
$ Input: n = 5
Output: [1,5,3,2,4]
💡 Note: Built using divide and conquer: odds from n=3 become [1,5,3], evens from n=2 become [2,4], combined to form beautiful array of length 5.

Constraints

  • 1 ≤ n ≤ 1000
  • It's guaranteed that for the given n, at least one valid answer exists.

Visualization

Tap to expand
Beautiful Array Problem: No Arithmetic Progressions AllowedInput: n = 4 → Output: Any permutation of [1,2,3,4] with no middle element as average1324i=0i=1i=2i=3Condition: For i < k < j, nums[k] ≠ (nums[i] + nums[j]) / 2Check: i=0, j=2, k=1nums[1]=3 ≠ (1+2)/2=1.5 ✓Check: i=0, j=3, k=1nums[1]=3 ≠ (1+4)/2=2.5 ✓Check: i=0, j=3, k=2nums[2]=2 ≠ (1+4)/2=2.5 ✓Beautiful Array: [1,3,2,4]
Understanding the Visualization
1
Input
Integer n = 4 (need permutation of [1,2,3,4])
2
Process
Use divide and conquer with odd/even transformation
3
Output
Beautiful array [1,3,2,4] with no arithmetic progressions
Key Takeaway
🎯 Key Insight: Use mathematical properties - if A is beautiful, then 2*A-1 and 2*A are also beautiful
Asked in
Google 15 Facebook 8
18.5K Views
Low Frequency
~25 min Avg. Time
892 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen