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 _anybeautiful array _nums of lengthn. There will be at least one valid answer for the given n.

Examples

Example 1

1
2
3
4
5
6


    
    
    Input: n = 4
    Output: [2,1,4,3]

Example 2

1
2
3
4
5
6


    
    
    Input: n = 5
    Output: [3,1,2,5,4]

Constraints

  • 1 <= n <= 1000

Solution

Method 1 – Divide and Conquer

Intuition

The key idea is to recursively build a beautiful array by separating numbers into odds and evens. By ensuring that all odd numbers are grouped together and all even numbers are grouped together, we avoid creating any triplet (i, k, j) where 2 * nums[k] == nums[i] + nums[j]. This works because the sum of two odd or two even numbers is always even, but the sum of an odd and an even is odd, so their average is never an integer in the other group.

Approach

  1. If n == 1, return [1].
  2. Recursively construct a beautiful array for the odd indices (1, 3, 5, …) and for the even indices (2, 4, 6, …).
  3. For the odd part, map each element x to 2*x - 1.
  4. For the even part, map each element x to 2*x.
  5. Concatenate the odd and even results to form the final array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
  vector<int> beautifulArray(int n) {
    if (n == 1) return {1};
    vector<int> ans, odd = beautifulArray((n + 1) / 2), even = beautifulArray(n / 2);
    for (int x : odd) ans.push_back(2 * x - 1);
    for (int x : even) ans.push_back(2 * x);
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func beautifulArray(n int) []int {
  if n == 1 {
    return []int{1}
  }
  odd := beautifulArray((n + 1) / 2)
  even := beautifulArray(n / 2)
  ans := make([]int, 0, n)
  for _, x := range odd {
    ans = append(ans, 2*x-1)
  }
  for _, x := range even {
    ans = append(ans, 2*x)
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
  public int[] beautifulArray(int n) {
    if (n == 1) return new int[]{1};
    int[] odd = beautifulArray((n + 1) / 2);
    int[] even = beautifulArray(n / 2);
    int[] ans = new int[n];
    int idx = 0;
    for (int x : odd) ans[idx++] = 2 * x - 1;
    for (int x : even) ans[idx++] = 2 * x;
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
  fun beautifulArray(n: Int): IntArray {
    if (n == 1) return intArrayOf(1)
    val odd = beautifulArray((n + 1) / 2)
    val even = beautifulArray(n / 2)
    val ans = IntArray(n)
    var idx = 0
    for (x in odd) ans[idx++] = 2 * x - 1
    for (x in even) ans[idx++] = 2 * x
    return ans
  }
}
1
2
3
4
5
6
7
8

class Solution:
  def beautifulArray(self, n: int) -> list[int]:
    if n == 1:
      return [1]
    odd = self.beautifulArray((n + 1) // 2)
    even = self.beautifulArray(n // 2)
    ans: list[int] = [2 * x - 1 for x in odd] + [2 * x for x in even]
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
  pub fn beautiful_array(n: i32) -> Vec<i32> {
    if n == 1 {
      return vec![1];
    }
    let odd = Self::beautiful_array((n + 1) / 2);
    let even = Self::beautiful_array(n / 2);
    let mut ans = Vec::with_capacity(n as usize);
    for &x in &odd {
      ans.push(2 * x - 1);
    }
    for &x in &even {
      ans.push(2 * x);
    }
    ans
  }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)