Beautiful arrangement ii

Array Math

61.0% acceptance

Feb 20, 2026

826

1059

Given two integers n and k, construct a list that contains n different positive integers ranging from 1 to n such that there are exactly k-1 distinct integers in the absolute differences between consecutive values.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn construct_array(n: i32, k: i32) -> Vec<i32> {
    let mut result = Vec::with_capacity(n as usize);
    // First part: 1, 2, ..., n-k (diffs all 1)
    for i in 1..=(n - k) {
      result.push(i);
    }
    // Second part: alternate hi, lo to get diffs k-1, k-2, ..., 1
    let (mut lo, mut hi) = (n - k + 1, n);
    let mut toggle = true; // true = push hi first
    while lo <= hi {
      if toggle {
        result.push(hi);
        hi -= 1;
      } else {
        result.push(lo);
        lo += 1;
      }
      toggle = !toggle;
    }
    result
  }
}