Beautiful array

Array Math Divide and Conquer

68.7% acceptance

Feb 25, 2026

1152

1593

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn beautiful_array(n: i32) -> Vec<i32> {
    // Divide and conquer: beautiful_array(n) = [2*x-1 for x in beautiful_array(ceil(n/2))] + [2*x for x in beautiful_array(floor(n/2))]
    // Base: [1]
    let mut res = vec![1i32];
    while res.len() < n as usize {
      res = res.iter().map(|&x| 2*x - 1)
        .chain(res.iter().map(|&x| 2*x))
        .filter(|&x| x <= n)
        .collect();
    }
    res
  }
}